简单数学问题之素数的判断及获取

1.素数的判断

#include <iostream>
using namespace std;
bool isPrime(int n){
   
    if(n<=1) return false;//大于1的
    for(int i=2;i*i<=n;i++)
    if(n%i==0) return false;//只能被1及本身整除的数
    return true;
}
int main(){
   
    int num;
    cin>>num;
    if(isPrime(num))
    cout<<num<<" is a prime!"<<endl;
    else cout<<num<<" is not a prime!"<<endl;
    return 0;
}

2.素数的获取

直接判断获取法

#include <iostream>
using namespace std;
int prime[101],num=0;;
bool isPrime(int n){
   
    if(n<=1) return false;
    for(int i=2;i*i<n;i++)
    if(n%i==0) return false;
    return true;
}
void getPrime(){
   
    for(int i=1;i<101;i++){
   //获取1-100的素数，判断再装入
        if(isPrime(i))
        prime[num++]=i;
    }
}
int main(){
   
    getPrime();
    for(int i=0;i<num;i++)
    if(i!=num-1)
    cout<<prime[i]<<",";
    else cout<<prime[i]<<endl;
    return 0;
}

埃氏筛法：筛去素数的倍数

#include <iostream>
using namespace std;
int prime[101],num=0;
bool isPrime[101]={
   0};//初始为false
void getPrime(){
   
    for(int i=2;i<101;i++){
   
        if(isPrime[i]==false)
        prime[num++]=i;//记录素数
        for(int j=i+i;j<101;j+=i)
        isPrime[j]=true;//筛去素数的倍数
    }
}
int main(){
   
    getPrime();
    for(int i=0;i<num;i++)
    if(i!=num-1)
    cout<<prime[i]<<",";
    else cout<<prime[i]<<endl;
    return 0;
}