质数判定与质数表的求解

866. 试除法判定质数

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定 n

个正整数 ai

，判定每个数是否是质数。

输入格式

第一行包含整数 n

。

接下来 n

行，每行包含一个正整数 ai

。

输出格式

共 n

行，其中第 i 行输出第 i 个正整数 ai

是否为质数，是则输出 Yes，否则输出 No。

数据范围

1≤n≤100

,
1≤ai≤231−1

输入样例：

2
2
6

输出样例：

Yes
No

 

代码：

#include 
#include 
#include 
 
using namespace std;
 
bool Is_primer(int val)
{
    if(val<2)
        return false;
    for(int i=2;i<=val/i;++i)
        if(val%i==0)
            return false;
    return true;
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int val;
        cin >> val;
        if(Is_primer(val))
            cout << "Yes\n";
        else 
            cout << "No\n";
    }
    return 0;
}

867. 分解质因数

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定 n

个正整数 ai

，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 n

。

接下来 n

行，每行包含一个正整数 ai

。

输出格式

对于每个正整数 ai

，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

1≤n≤100

,
2≤ai≤2×109

输入样例：

2
6
8

输出样例：

2 1
3 1
 
2 3
 

coding:

#include 
#include 
 
using namespace std;
 
map<int,int> get_primer_factor(int val)
{
    map<int,int> mp;
    for(int i=2;i<=val/i;++i)
        if(val%i==0)
        {
            while(val%i==0)
            {
                mp[i]++;
                val/=i;
            }
        }
    if(val>1)
        mp[val]=1;
    return mp;
}
 
int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int val;
        cin >> val;
        map<int,int> mp=get_primer_factor(val);
        for(auto a:mp)
            cout << a.first << ' ' << a.second << endl;
        cout << endl;
    }
    return 0;
}

868. 筛质数

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定一个正整数 n

，请你求出 1∼n

中质数的个数。

输入格式

共一行，包含整数 n

。

输出格式

共一行，包含一个整数，表示 1∼n

中质数的个数。

数据范围

1≤n≤106

输入样例：

8

输出样例：

4

coding:

coding first: 埃氏筛法：O(n*loglogn)

//coding first: 埃氏筛法：
#include 
 
using namespace std;
 
const int N = 1e6+10;
int p[N],num=0;
bool hs[N]={0};
 
void get_primer_table(int val)
{
    for(int i=2;i<=val;++i)
    {
        if(hs[i]==0)
        {
            p[num++]=i;
            for(int j=i+i;j<=val;j+=i)
                hs[j]=1;
        }
    }
}
 
int main()
{
    int n;
    cin >> n;
    get_primer_table(n);
    cout << num << endl;
    return 0;
}

coding second:欧拉筛法，线性筛法：O(n)

 * 如果i是素数，那么j==num-1的时候，一定会退出循环；
 * 如果i不是素数，那么j  * 所以for循环的判断条件不用加上j  * 至于为什么会加上i*p[j]<=n,原因是让p[j]*i的值不超过n，
 * 以使hs数组不越界。

//coding second:欧拉筛法，线性筛法
#include 
#include 
#include 
 
using namespace std;
 
const int N = 1e6+10;
int p[N] , num=0;
bool hs[N]={0};
 
/**
 * 如果i是素数，那么j==num-1的时候，一定会退出循环；
 * 如果i不是素数，那么j
 * 所以for循环的判断条件不用加上j
 * 至于为什么会加上i*p[j]<=n,原因是让p[j]*i的值不超过n，
 * 以使hs数组不越界。
*/
 
void get_primers(int n)
{
    for(int i=2;i<=n;++i)
    {
        if(!hs[i])  p[num++]=i;
        for(int j=0;p[j]<=n/i;++j)
        {
            hs[p[j]*i]=1;
            if(i%p[j]==0)
                break;
        }
    }
}
 
int main()
{
    int n;
    cin >> n;
    get_primers(n);
    cout << num << endl;
    return 0;
}