欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT乙级1013数素数

程序员文章站 2024-03-15 15:23:54
...

题目如下:

令 P ​i ​​ 表示第 i 个素数。现任给两个正整数 M≤N≤10 ​4 ​​ ,请输出 P ​M ​​ 到 P ​N ​​ 的所有素数。

输入格式:
输入在一行中给出 M 和 N,其间以空格分隔。

输出格式:

输出从 P ​M ​​ 到 P ​N ​​ 的所有素数,每 10 个数字占 1 行,其间以空格分隔,但行末不得有多余空格。

输入样例:
5 27
输出样例:
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

代码如下:

#include <iostream>
using namespace std;
bool isprime(int a)
{
    for(int i=2;i*i<=a;i++)
        if(a%i==0) return false;
        return true;
}
int main()
{
    int m,n,flag=1;
    cin>>m>>n;
    int num=2,cnt=0,a[10000]={0};
    while(cnt<n)
    {
        if(isprime(num))
        {
            a[cnt++]=num;
        }
        num++;
    }
    cnt=0;
    for(int i=m-1;i<n;i++)
    {
        cnt++;
        cout<<a[i];
        if(cnt%10!=0&&cnt!=n-m+1) cout<<" ";
        if(cnt%10==0) cout<<endl;
    }
    return 0;
}

求素数的模板函数:

bool isprime(int a)
{
    for(int i=2;i*i<=a;i++)
        if(a%i==0) return false;
        return true;
}

总结:
求素数有两种方法:筛选法和开根号法

  • 筛选法:从小到大筛去一个已知素数的所有倍数。依次删除可被2整除,3整除。。。。的数字,剩下的则为素数 。

  • 开根号法:如果一个数(>2),对这个数求平方根,如果这个数能被这个数的平方根到2之间的任何一个(只要有一人就行)整除说明就不是质数,如果不能就说明是质数!