求n以内的素数

求n以内素数。

 

素数又称质数，它是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。

 

有两种方法：筛选法和开根号法

 

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

 

开根号法：如果一个数（>2），对这个数求平方根，如果这个数能被这个数的平方根到2之间的任何一个（只要有一人就行）整除说明就不是质数，如果不能就说明是质数！

原理：假如一个数N是合数，它有一个约数a,a×b=N，则a、b两个数中必有一个大于或等于根号N，一个小于或等于根号N。因此，只要小于或等于根号N的数（1除外）不能整除N，则N一定是素数。

 

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

void getPrime0(int);
void getPrime(int);
void getPrime2(int);
void getPrime3(int);

int main(){
    cout << "Hello world!" << endl;
    int n = 100;
    getPrime0(n); 
    getPrime(n);
    getPrime2(n);
    getPrime3(n);
    system("pause");
    return 0;
} 

//求n以内的素数
//素数又称质数，它是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。 
//算法：筛选法，从小到大筛去一个已知素数的所有倍数。依次删除可被2整除，3整除。。。。的数字，剩下的则为素数 
void getPrime0(int n){
     int i,j;
     bool m;
     for(i = 1; i <= n; i ++){
           m = true;
           for(j = 2; j < i; j ++){
                 if(i % j == 0){
                      m = false;
                      break;
                 }
           }
           if(m){
                 cout << i << " "; 
           }
     }
     cout << endl;
}

//同上 
void getPrime(int n){
    int a[n + 1];
    for(int i = 1; i < n + 1; i ++){
            a[i] = 1;//用1对数组进行标记
    }
    for(int i = 2; i < n + 1; i ++){
            for(int j = 2; j < n + 1; j ++){
                    if(a[j] == 1 && j % i == 0 && j / i != 1){//若还未标记，且是如2的倍数，并不是如2本身 
                            a[j] = 0;//非素数用0标记，最后仍未1的则为素数 
                    }
            }        
    } 
    for(int i = 1; i < n + 1; i ++){
            if(a[i] == 1){
                    cout << i << " ";
            }
    }   
    cout << endl;           
} 

//等同于getPrime(int n) 
void getPrime2(int n){
     int a[n + 1],i,j;
     for(i = 1; i < n + 1; i ++){
           a[i] = 1;
     }
     for(i = 2; i < n + 1; i ++){
           if(a[i] == 1){
                   for(j = i + i; j < n + 1; j = j + i){
                         if(j % i == 0){
                              a[j] = 0;
                         }
                   }
           }
     } 
     for(i = 1; i < n + 1; i ++){
            if(a[i] == 1){
                    cout << i << " ";
            }
    }   
    cout << endl;
}

//开根号法 
//算法：如果一个数（>2），对这个数求平方根，如果这个数能被这个数的
//平方根到2之间的任何一个（只要有一人就行）整除说明就不是质数，
//如果不能就说明是质数！
//原理：假如一个数N是合数，它有一个约数a,a×b=N
//则a、b两个数中必有一个大于或等于根号N，一个小于或等于根号N。
//因此，只要小于或等于根号N的数（1除外）不能整除N，则N一定是素数。

void getPrime3(int n){
     int a[n + 1],i,j,k;
     for(i = 1; i < n; i ++){
           k = (int)sqrt(i);
           for(j = 2; j <= k; j ++){
                 if(i % j == 0){
                      break;
                 }
           }
           if(j > k){
                cout << i << " ";
           }
     }
}

 

评论

2 楼 maidoudao 2011-12-25  

nikalan 写道

当n = 6659时 开方的方法还能算 其他都效率太低

n再大 开方的算法也挂了 这两种求素数算法有待优化

你说的确实很对，那有没有什么优化的方法呢？

1 楼 nikalan 2011-12-20  

当n = 6659时 开方的方法还能算 其他都效率太低

n再大 开方的算法也挂了 这两种求素数算法有待优化