如何判断素数(C++版)

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

1.对于判断一个数n是否为素数,最朴素的方法是按素数的定义,试除以从2开始到m-1的整数,如果无一例外地不能整除,则该数一定是素数。

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    for(int i=2; i<n; i++){
        if(n%i == 0){
            cout << n << " isn't a prime" << endl;
            return 1;
        }
    }
    cout << n << " is a prime" << endl;
    return 0;
}

2.想一想,若2都不能除尽,还要试4, 6, 8, …吗?若3都不能除尽,还要试9, 15, 21, …吗?等等。一个数,如果有因子的话,那么在它的平方根数以内就应该有,否则就没有因子。所以必定有一个因子不大于m的平方根。故判断m是否为素数,只要试除到m的平方根就可以了,不必一直到m-1。

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int n;
    cin >> n;
    for(int i=2; i<=sqrt(n); i++){
        if(n%i == 0){
            cout << n << " isn't a prime" << endl;
            return 1;
        }
    }
    cout << n << " is a prime" << endl;
    return 0;
}

3.另一种判断素数的方法–筛法。从文件prime.txt中读入一些整数,然后判断其是否为素数。从2开始的某个连续整数集合,留下2,除去所有2的倍数,留下3,除去所有3的倍数,留下5,再除去所有5的倍数,如此等等。留下某个最先遇到的素数,将其所有的倍数从该数集中去掉。最后,数集中就全是素数了。接下来,要判断一个数是否为素数,可以该数为下标,访问素数集合。如果是,则为素数,否则不是素数。

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int main(){
    vector<int> prime(10000, 1);
    for(int i=2; i<100; i++){
        if(prime[i]){
            for(int j=i; i*j<10000; j++)
                prime[i*j] = 0;
        }
    }
    ifstream in("prime.txt");
    for(int k; in>>k && k>1 && k<10000; )
        cout << k << " is " << (prime[k] ? "":"not ") << "a prime." << endl;
    return 0;
}

程序中,先将10000个向量元素都赋初值1,凡是该下标的元素为1的,则为素数。所以初始状态下,所有整数都是素数,在这基础上将不是素数的数筛掉(将对应元素置0)。在筛的过程中,用了“若为素数,必有因子小于其平方根”的思想,10000个数,过滤因子只要到100,就能保证10000以内全是素数了。

在程序中,对于3来说,要去掉所有3的因子,包括6、12、18等,但事实上,偶数在上一轮中已经作为2的倍数而去掉了。所以,这个过程还有一些重复操作,算法还有可改进的地方。

点这里可以跳转到人工智能网站