求n以内的素数求n以内素数。?素数又称质数，它是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为
求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 << " "; } }}?
1 楼 nikalan 2011-12-20 当n = 6659时 开方的方法还能算 其他都效率太低n再大 开方的算法也挂了 这两种求素数算法有待优化 2 楼 maidoudao 2011-12-25 nikalan 写道当n = 6659时 开方的方法还能算 其他都效率太低
n再大 开方的算法也挂了 这两种求素数算法有待优化
你说的确实很对，那有没有什么优化的方法呢？