【求助】c++统计质数问题怎么做？ - 编程论坛

#2

ZJYTY2019-01-25 13:48

程序代码：

#include<iostream>
#include<vector>
#include<time.h>

using namespace std;

class PrimePalindrome
{
public:
    void PrimeNumbers();
    void showNumbers();
    void inputNum();
private:
    int numbers;
    vector<int> inPut;
    vector<int> Prime;
};

void PrimePalindrome::PrimeNumbers()
{
    int a = 0;
    int i;
    vector<int>::iterator itr = inPut.begin();
    for (itr; itr != inPut.end(); ++itr)
    {
        for (i = 2; i <= (*itr); ++i)
        {
            if ((*itr) % i == 0)
                break;
        }
        if (i == (*itr)){
            Prime.push_back(*itr);
        }
    }
}

void PrimePalindrome::showNumbers()
{
    cout << "质数列表：" << endl;
    for (vector<int>::iterator itr = Prime.begin(); itr != Prime.end(); ++itr)
    {
        cout << *itr << endl;
    }
}
void PrimePalindrome::inputNum()
{
    int inputNumber;
    cout << "Input the number of number : ";
    cin >> numbers;
    while (!getchar());
    for (int i = 0; i < numbers; ++i)
    {
        cin >> inputNumber;
        while (!getchar());
        inPut.push_back(inputNumber);
    }
}

int main()
{
    clock_t start, finish;
    double totaltime;

    PrimePalindrome pp;
    pp.inputNum();
    start = clock();

    pp.PrimeNumbers();
    pp.showNumbers();

    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "\n此程序的运行时间为" << totaltime << "秒！" << endl;
    getchar();
}

只有本站会员才能查看附件，请登录

#3

lyb6612019-01-25 19:25

bool isPrime(int n)
{
    for(int i=2;i<=(int)sqrt(n);i++){
        if(n%i==0)
            return false;
    }
    return true;
}

#4

幽竹烟雨2019-01-30 22:17

建议不要搞太多对新人不友好的东西，下面上我的代码（建议楼主好好看看，不要为抄答案而忽略注释，判素这个函数真的很基础又很重要，一定要好好理解哦~）

#include<bits/stdc++.h>//万能头文件，不过并不包括<windows.h>库等好玩的东西
using namespace std;
int a[1000000];//数组是不是开太大了？
bool lele(int n)//判素神器
{
    if(n==1||n==0) return false;//要考虑 0、1不是素数的情况
    for(int i=2;i<=sqrt(n);i++)//进行列举排除，sqrt(n)是取n的平方根，提高效率
    {
        if(n%i==0) return false;//如果i能被n整除，说明i是n的因数,n就不是素数，返回假
    }
    return true;//循环结束后，说明n是素数，返回真
}
int main()
{
    ios::sync_with_stdio(false);//个人习惯，您可以选择注释掉它
    int n,i,o=0;
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>a[i];//输入这几个数
    for(i=1;i<=n;i++)
    {
        if(lele(a[i]))//逐一进行判断，如果满足条件（是素数），就输出
        {
            if(o==0)//为了防止输出后面多了空格，我是这样处理的
            {
                cout<<a[i];
                o++;
            }
            else cout<<" "<<a[i];
        }
    }
    return 0;//完美地结束
}

#5

流照君2019-02-28 22:26

看了楼上的觉得有必要贴一下自己的代码了；
因为楼上的都是一个个判断；
埃式素数筛选才是时间复杂都最快的
楼主可以去百度一下
#include<iostream>
#include<string.h>
using namespace std;
#define MAX_N 100000
bool is_prime[MAX_N];
int prim[MAX_N];

int sieve(int n)
{
   int num=0;
    for(int i=2;i<=n;i++)
        is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i])
        {
            prim[num++]=i;
            for(int j=2*i;j<=n;j+=i)
                is_prime[j]=false;
        }
    }
    return num;
}
int main()
{
    int N;
    cin>>N;

        memset(prim,0,sizeof(prim));
         for(int i=0;i<sieve(N);i++)
    cout<<prim[i]<<endl;

}