求素数（质数）算法

（不想做题了。。。。。整理一些资料吧）

求素数（质数）算法

如果一个正整数只有两个因子，1和p,则p为素数

1、根据概念判断

bool isPrime(int n)
{
    if(n < 2) return false;

    for(int i = 2; i < n; ++i)
        if(n%i == 0) return false;

    return true;
}

#include<stdio.h>
int is_sushu(int x)//是素数就返回1，否则返回0
{
    if(x==1)//1既不是素数也不是合数
        return 0;
    else if(x==2)//2是素数
        return 1;
    else
    {
        for(int i=2; i<=sqrt(x); i++)//sqrt降低时间复杂度
            if(x%i==0)//如果x能被i整除，说明x不是素数
                return 0;
        return 1;//是素数返回1
    }
}

2、去掉偶数的判断

bool isPrime(int n)
{
    if(n < 2) return false;
    if(n == 2) return true;

    for(int i = 3; i < n; i += 2)
        if(n%i == 0) return false;

    return true;
}

3、进一步减少判断的范围 sqrt(n)

bool isPrime(int n)
{
    if(n < 2) return false;
    if(n == 2) return true;

    for(int i = 3; i*i <= n; i += 2)
        if(n%i == 0) return false;

    return true;
}

#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 10000//N的大小可以根据需要变化
int a[N];//利用数组的下标记录要判断的数字
void is_sushu()
{
    memset(a,0,sizeof(a));//对数组a进行初始化为0，不是素数的标记为1，剩下为0的就是素数了
    a[1]=1;//1既不是素数也不是合数，先标记为0
    for(int i=2; i<=sqrt(N); i++)
    {
        if(a[i]==0)//如果i是素数
        {
            for(int j=2; j*i<=N; j++) //循环标记的范围是i*j<N
            {
                a[i*j]=1;//如果i是素数，那么i*j肯定不是素数
            }
        }
    }//最终所有非素数都标记为1，素数都标记为0
}

4、打表法求素数模板

prime[0]=prime[1]=1;  
     for(i = 2; i <1000; i++)  
         for(j = i * i; j <1000000; j+= i)  
             prime[j] = 1;

5、一般线性筛选求素数

void make_prime()  {        
    memset(prime, 1, sizeof(prime));  
    prime[0]=false;       
    prime[1]=false;       
    int N=31700;        
    for (int i=2;  i<N;  i++)           
      if (prime[i]) {            
        primes[++cnt ]=i;       
        for (int k=i*i; k<N; k+=i)          
            prime[k]=false;         
      }        
    return;  
}

6、快速线性筛选求素数

#include<iostream>  
using namespace std;      
const long N = 200000;     
long prime[N] = {0},num_prime = 0;      
int isNotPrime[N] = {1, 1};     
int main()      
{       
        for(long i = 2 ; i < N ; i ++)         
        {              
        if(! isNotPrime[i])                 
            prime[num_prime ++]=i;    
        //关键处1          
        for(long j = 0 ; j < num_prime && i * prime[j] <  N ; j ++)  
            {                 
                isNotPrime[i * prime[j]] = 1;    
            if( !(i % prime[j] ) )  //关键处2                    
                break;             
        }          
    }          
    return 0;     
}

7、推荐

half=SIZE/2;   
int sn = (int) sqrt(SIZE);   
for (i = 0; i < half; i++)   
   p[i] = true;// 初始化全部奇数为素数。p[0]对应3，即p[i]对应2*i+3   
for (i = 0; i < sn; i++) {      
if(p[i])//如果 i+i+3 是素数  
{       
    for(k=i+i+3, j=k*i+k+i; j < half; j+=k)   
    // 筛法起点是 p[i]所对应素数的平方 k^2                                          
    // k^2在 p 中的位置是 k*i+k+i  
    //    下标 i         k*i+k+i  
    //对应数值 k=i+i+3   k^2           
       p[j]=false;   
}   
}   
//素数都存放在 p 数组中，p[i]=true代表 i+i+2 是素数。  
//举例，3是素数，按3*3,3*5,3*7...的次序筛选，因为只保存奇数，所以不用删3*4，3*6....

秒客网

求素数（质数）算法

相关文章