求素数的一个快速算法
求素数的一个快速算法
素数筛选法是这样的：
1.开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false.
2.然后：
for (j = 2; j <= sqrt(i); j++)
if (j%i == 0)
{
temp[i] = false; // 非素数
break;
}
3.最后输出bool数组中的值为true的单元的下标，就是所求的n以内的素数了。
原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质数的倍数筛掉。
一个简单的筛素数的过程：n=30。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
第 1 步过后2 4 … 28 30这15个单元被标成false,其余为true。
第 2 步开始：
i=3; 由于prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]标为false.
i=4; 由于prime[4]=false,不在继续筛法步骤。
i=5; 由于prime[5]=true, 把prime[10],[15],[20],[25],[30]标为false.
i=6>sqrt(30)算法结束。
第 3 步把prime[]值为true的下标输出来：
for(i=2; i<=30; i++)
if(prime[i]) printf(“%d “,i);
结果是 2 3 5 7 11 13 17 19 23 29
这就是最简单的素数筛选法，对于前面提到的10000000内的素数，用这个筛选法可以大大的降低时间复杂度。把一个只见黑屏的算法优化到立竿见影，一下就得到结果。
1 #include <iostream> 2 #include <cmath> 3 #include <ctime> 4 5 void select(bool * temp, int num, int run); //筛选算法 6 void Prime(bool * temp, int num); // 求素数算法 7 8 int main() 9 { 10 using namespace std; 11 int i, num; 12 clock_t t; 13 std::cout << "enter an integer: "; 14 std::cin >> num; 15 t = clock(); 16 bool *temp = new bool [num * sizeof(bool)]; 17 for (i = 0; i < num; i++) 18 temp[i] = true; 19 20 select(temp, num, 2);// 偶数筛选，如果上一步进行初始化的时候就设置，可能效率更高 21 select(temp, num, 3);// 3倍数筛选 22 Prime(temp, num); 23 24 t = clock() - t; 25 cout << "using time is " << (double)t / CLOCKS_PER_SEC << " seconds.\n"; 26 for (i = 1; i < num; i++) 27 if (temp[i]) 28 std::cout << i << " "; 29 30 return 0; 31 } 32 33 void select(bool * temp, int num, int run) 34 { 35 for (int i = 2; i*run < num; i++) //对素数进行倍数筛选 36 temp[i*run] = false; 37 } 38 39 void Prime(bool * temp, int num) 40 { 41 int i, j; 42 for (i = 2; i < num; i++) 43 { 44 if (temp[i]) //对筛选后的结果进行求素数 45 { 46 for (j = 2; j <= sqrt(i); j++) 47 if (j%i == 0) 48 { 49 temp[i] = false; 50 break; 51 } 52 select(temp, num, i); //如果为素数，那该素数的倍数必然非素数，筛选！ 53 } 54 } 55 }
#仅供参考！仅供参考！仅供参考！#
对初学者仅供参考，大神可以贴出更好的算法，谢谢~
posted on 2017-12-13 19:49 weibin_caffe 阅读(…) 评论(…) 编辑 收藏