Php筛选法求素数

求素数的算法
1. 定义
素数又称质数，是指只能被1和它本身整除的自然数，如2、3、5、7、11等，而4、6、8、9等都不是素数。

2. 筛法
筛法是一种较为简单的求素数的算法，主要原理是先假设所有数都是素数，然后从小
到大开始筛选，将所有能够整除当前数字的数标记为合数，剩余的就是素数。

具体步骤如下：
（1）初始化数组：将从2到n的所有整数存入数组中，初始时都标记为素数。

（2）循环遍历数组：从2开始循环遍历数组，将当前数字标记为素数，然后将所有能够整除当前数字的数标记为合数。

（实际上只需要循环到sqrt(n)即可）
（3）输出素数：遍历数组，输出所有标记为素数的数。

3. 质数判定法
如果只需要判断某一个给定的数是否是素数，那么可以采用质数判定法。

常见的质数
判定法有以下几种：
（1）试除法：从2开始到sqrt(n)依次尝试除n，如果能够整除则不是素数，否则是
素数。

这种方法速度较慢，但实现简单。

（2）根号判定法：如果一个数n不是素数，那么n可以表示为两个整数的乘积，即n = x * y。

这两个整数必然有至少一个小于等于sqrt(n)。

因此，只需要判断是否存在小于等于sqrt(n)的因数即可。

（3）费马小定理：如果n是素数，那么对于任意整数a，a^(n-1) mod n = 1。

根据这个定理，我们可以随机选取一些a进行计算，如果a^(n-1) mod n 不等于 1，则n一定不是素数，否则n可能是素数。

（4）米勒-拉宾素性判定法：该方法是一种基于费马小定理的扩展算法。

具体实现过
程较为复杂，但速度较快，能够判断很大的素数。

素数（质数）判断的五种方法素数判断是编写程序过程中常见的问题，所以今天我简单梳理一下常用的素数判断方法。

素数的介绍素数定义质数(prime number)又称素数，有无限个。

一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。

根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积;而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。

最小的质数是2。

--------360百科第一种：暴力筛选法思路分析根据素数的定义，我们可以简单地想到：若要判断n是不是素数，我们可以直接写一个循环（i从2到n-1，进行n%i运算，即n能不能被i整除，如被整除即不是素数。

若所有的i 都不能整除，n即为素数）。

代码实现booleanisPrime(int n){for(inti=2;i<n;i++){if(n%i==0){returnfalse;break;}}returntrue ;}时间复杂度：O(n)这个时间复杂度乍一看并不乐观，我们就简单优化一下。

booleanisPrime(int n){for( i=2; i<=(int)sqrt(n);i++){if(n%i==0){returnfalse;break;}}returntrue;}时间复杂度：O(sqrt(n))优化原理：素数是因子为1和本身，如果num不是素数，则还有其他因子，其中的因子，假如为a,b.其中必有一个大于sqrt(num) ，一个小于sqrt（num）。

所以必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。

即一个合数一定含有小于它平方根的质因子。

第二种：素数表筛选法素数表的筛选方法一看就知道素数存储在一个表中，然后在表中查找要判断的数。

找到了就是质数，没找到就不是质数。

思路分析如果一个数不能整除比它小的任何素数，那么这个数就是素数对了，这个方法效率不高，看看就知道思路了。

例6、用筛法求出100以内的全部素数，并按每行五个数显示。

【问题分析】⑴把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）；⑵在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）；⑶从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置0；⑷让p=p+1，重复执行第②、③步骤，直到minp>Trunc(sqrt(N)) 为止；⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。

用筛法求素数的过程示意如下（图中用下划线作删去标志）：① 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 ｛置数｝② 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被2整除的数}③ 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被3整除的数}……2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被整除的数}Program Exam53;const N=100;type xx=1 .. N; {自定义子界类型xx（类型名）}Var a: array[xx] of boolean; i,j: integer;BeginFillchar(a,sizeof(a),true);a[1] := False;for i:=2 to Trunc(sqrt(N)) doif a[I] thenfor j := 2 to N div I doa[I*j]:= False;t:=0;for i:=2 to N doif a[i] thenBeginwrite(a[ i ]:5); inc(t);if t mod 5=0 then writelnend;End.【例3】输入十个正整数，把这十个数按由大到小的顺序排列（将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序中的“简单选择排序”是一种较简单的方法）分析：要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……；因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数。

例6、用筛法求出100以内的全部素数，并按每行五个数显示。

【问题分析】⑴把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）；⑵在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）；⑶从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置0；⑷让p=p+1，重复执行第②、③步骤，直到minp>Trunc(sqrt(N)) 为止；⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。

用筛法求素数的过程示意如下（图中用下划线作删去标志）：①2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 ｛置数｝②2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被2整除的数}③2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被3整除的数}……2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被整除的数}Program Exam53;const N=100;type xx=1 .. N; {自定义子界类型xx（类型名）}V ar a: array[xx] of boolean; i,j: integer;BeginFillchar(a,sizeof(a),true);a[1] := False;for i:=2 to Trunc(sqrt(N)) doif a[I] thenfor j := 2 to N div I doa[I*j]:= False;t:=0;for i:=2 to N doif a[i] thenBeginwrite(a[ i ]:5); inc(t);if t mod 5=0 then writelnend;End.【例3】输入十个正整数，把这十个数按由大到小的顺序排列（将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序中的“简单选择排序”是一种较简单的方法）分析：要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……；因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数。

筛法--求1到100的所有素数⽤筛法求出100以内的全部素数，并按每⾏五个数显⽰我们知道⼀个合数可以分解了⼏个质数想乘，从2开始知道根号下n每次判断⼀个数是否为素数，如果为素数，就把所有能被这个数整除的数排除，即不是素数。

⾸先是⼀个判断素数的函数1bool sushu(int x)2 {3if (x==2)4return true;5for (int i = 2;i <= sqrt(x);i++)6 {7if (x%i==0)8return false;9 }10return true;11 }把能被素数整除得数排除1for (int i = 2;i <= sqrt(n);i++)2 {3if (sushu(i))4 {5for (int j= 2;j <= n/i;j++)6 {7 a[i*j]=false;8 }9 }10 }完整代码：1 #include <iostream>2 #include <cstdio>3 #include <cstring>4 #include <math.h>5 #include <algorithm>6 #include <iomanip>7using namespace std;8bool sushu(int x)9 {10if (x==2)11return true;12for (int i = 2;i <= sqrt(x);i++)13 {14if (x%i==0)15return false;16 }17return true;18 }19int main()20 {21int const n = 100;22bool a[10000];23 memset(a,true,sizeof(a));24 a[1]=false;25for (int i = 2;i <= sqrt(n);i++)26 {27if (sushu(i))28 {29for (int j= 2;j <= n/i;j++)30 {31 a[i*j]=false;32 }33 }34 }35int ans=0;36for(int i = 1;i <= n;i++) 37 {38if (a[i]){39 printf ("%-5d",i);40 ans++;41 }42if (ans==5)43 {44 ans=0;45 cout<<endl;46 }47 }48return0;49 }。

素数筛选分析及伪素数通项公式（1）素数筛选程序Option ExplicitSub 素数筛选()Dim MyArray() As VariantDim Arr() As StringDim Temp() As StringDim i As VariantDim r As VariantDim j As VariantDim n As Variantn = Sheet1.Range("B1") '声明动态数组。

ReDim MyArray(n)For i = 1 To nMyArray(i) = pu(i)Next iOn Error Resume NextFor j = 1 To nTemp = Filter(Arr, MyArray(j))If UBound(Temp) < 0 Thenr = r + 1ReDim Preserve Arr(1 To r)Arr(r) = MyArray(j)End IfNextSheet1.Range("a1").Resize(r, 1) = Application.Transpose(Arr)Sheet1.Range("C1") = UBound(Arr)'Sheet1.Range("a1").Resize(1, r) = Arr'Sheet1.Range("f1") = Join(Arr, ",")End SubFunction SZU(n As Variant, k As Variant) As VariantDim MyArray() As VariantDim Arr() As StringDim Temp() As StringDim i As VariantDim r As VariantDim j As VariantDim m As VariantDim d As Variantn = n + Int(0.25 * n)ReDim MyArray(n)For i = 1 To nMyArray(i) = pu(i)Next iOn Error Resume NextFor j = 1 To nTemp = Filter(Arr, MyArray(j))If UBound(Temp) < 0 Thenr = r + 1ReDim Preserve Arr(1 To r)Arr(r) = MyArray(j)End IfNextSheet1.Range("a1").Resize(r, 1) = Application.Transpose(Arr)Sheet1.Range("C1") = UBound(Arr)'Sheet1.Range("a1").Resize(1, r) = ArrSZU = Arr(k)End FunctionFunction pu(Y As Variant) As VariantDim d As Variantd = 3.14159265358979pu = 3 * Y + 3 * (Sin(0.5 * d * Y)) ^ 2 + (-1) ^ YIf qp(pu) = 0 Thenpu = 5Elsepu = 3 * Y + 3 * (Sin(0.5 * d * Y)) ^ 2 + (-1) ^ YEnd IfEnd FunctionFunction p(m As Variant, W As Variant) As VariantIf W >= m Thenp = 1End IfIf m / W = Int(m / W) And W < m Thenp = 0Elsep = 1End IfEnd FunctionFunction qp(m As Variant) As VariantDim s As Long, s1 As Long, s2 As Long, s3 As Long, s4 As Long, s5 As Long, s6 As LongDim s7 As Long, s8 As Long, s9 As Long, s10 As Long, s11 As Long, s12 As Long, s13 As Long Dim s14 As Long, s15 As Long, s16 As Long, s17 As Long, s18 As Long, s19 As LongDim s20 As Long, s21 As Long, s22 As Long, s23 As Long, s24 As Long, s25 As LongDim s26 As Long, s27 As Long, s28 As Long, s29 As Long, s30 As Long, s31 As Longs = p(m, 5) * p(m, 7) * p(m, 11) * p(m, 13) * p(m, 17) * p(m, 19) * p(m, 23) * p(m, 29) * p(m, 31) * p(m, 37) * p(m, 41) * p(m, 43) * p(m, 47) * p(m, 53) * p(m, 59) * p(m, 61) * p(m, 67) * p(m, 71) * p(m, 73) * p(m, 79) * p(m, 83) * p(m, 89) * p(m, 97)s1 = p(m, 101) * p(m, 103) * p(m, 107) * p(m, 109) * p(m, 113) * p(m, 127) * p(m, 131) * p(m, 137) * p(m, 139) * p(m, 149) * p(m, 151) * p(m, 157) * p(m, 163) * p(m, 167) * p(m, 173) * p(m, 179) * p(m, 181) * p(m, 191)s2 = p(m, 193) * p(m, 197) * p(m, 199) * p(m, 211) * p(m, 223) * p(m, 227) * p(m, 229) * p(m, 233) * p(m, 239) * p(m, 241) * p(m, 251) * p(m, 257) * p(m, 263) * p(m, 269) * p(m, 271) * p(m, 277) * p(m, 281) * p(m, 283)s3 = p(m, 293) * p(m, 307) * p(m, 311) * p(m, 313) * p(m, 317) * p(m, 331) * p(m, 337) * p(m, 347) * p(m, 349) * p(m, 353) * p(m, 359) * p(m, 367) * p(m, 373) * p(m, 379) * p(m, 383) * p(m, 389) * p(m, 397) * p(m, 401)s4 = p(m, 409) * p(m, 419) * p(m, 421) * p(m, 431) * p(m, 433) * p(m, 439) * p(m, 443) * p(m, 449) * p(m, 457) * p(m, 461) * p(m, 463) * p(m, 467) * p(m, 479) * p(m, 487) * p(m, 491) * p(m, 499) * p(m, 503) * p(m, 509)s5 = p(m, 521) * p(m, 523) * p(m, 541) * p(m, 547) * p(m, 557) * p(m, 563) * p(m, 569) * p(m, 571) * p(m, 577) * p(m, 587) * p(m, 593) * p(m, 599) * p(m, 601) * p(m, 607) * p(m, 613) * p(m, 617) * p(m, 619) * p(m, 631)s6 = p(m, 641) * p(m, 643) * p(m, 647) * p(m, 653) * p(m, 659) * p(m, 661) * p(m, 673) * p(m, 677) * p(m, 683) * p(m, 691) * p(m, 701) * p(m, 709) * p(m, 719) * p(m, 727) * p(m, 733) * p(m, 739) * p(m, 743) * p(m, 751)s7 = p(m, 757) * p(m, 761) * p(m, 769) * p(m, 773) * p(m, 787) * p(m, 797) * p(m, 809) * p(m, 811) * p(m, 821) * p(m, 823) * p(m, 827) * p(m, 829) * p(m, 839) * p(m, 853) * p(m, 857) * p(m, 881) * p(m, 883) * p(m, 857)s8 = p(m, 859) * p(m, 863) * p(m, 877) * p(m, 907) * p(m, 911) * p(m, 919) * p(m, 929) * p(m, 937) * p(m, 941) * p(m, 947) * p(m, 953) * p(m, 967) * p(m, 971) * p(m, 977) * p(m, 983) * p(m, 991) * p(m, 997) * p(m, 1009)s9 = p(m, 1013) * p(m, 1019) * p(m, 1021) * p(m, 1031) * p(m, 1033) * p(m, 1039) * p(m, 1049) * p(m, 1051) * p(m, 1061) * p(m, 1063) * p(m, 1069) * p(m, 1087) * p(m, 1091) * p(m, 1093) * p(m, 1097) * p(m, 1103) * p(m, 1109)s10 = p(m, 1303) * p(m, 1307) * p(m, 1217) * p(m, 1223) * p(m, 1117) * p(m, 1123) * p(m, 1129) * p(m, 1151) * p(m, 1153) * p(m, 1163) * p(m, 1171) * p(m, 1181) * p(m, 1187) * p(m, 1193) * p(m, 1201) * p(m, 1213) * p(m, 1229)s11 = p(m, 1231) * p(m, 1237) * p(m, 1249) * p(m, 1259) * p(m, 1277) * p(m, 1279) * p(m, 1283) * p(m, 1289) * p(m, 1291) * p(m, 1297) * p(m, 1301) * p(m, 1319) * p(m, 1321) * p(m, 1327) * p(m, 1361) * p(m, 1367) * p(m, 1373)s12 = p(m, 1381) * p(m, 1399) * p(m, 1409) * p(m, 1423) * p(m, 1427) * p(m, 1429) * p(m, 1433) * p(m, 1439) * p(m, 1447) * p(m, 1451) * p(m, 1453) * p(m, 1459) * p(m, 1471) * p(m, 1481) * p(m, 1483) * p(m, 1487) * p(m, 1489)s13 = p(m, 1493) * p(m, 1499) * p(m, 1511) * p(m, 1523) * p(m, 1531) * p(m, 1543) * p(m, 1549) * p(m, 1553) * p(m, 1559) * p(m, 1567) * p(m, 1571) * p(m, 1579) * p(m, 1583) * p(m, 1597) * p(m, 1601) * p(m, 1607) * p(m, 1609)s14 = p(m, 1613) * p(m, 1619) * p(m, 1621) * p(m, 1627) * p(m, 1637) * p(m, 1657) * p(m, 1663) *p(m, 1667) * p(m, 1669) * p(m, 1693) * p(m, 1697) * p(m, 1699) * p(m, 1709) * p(m, 1721) * p(m, 1723) * p(m, 1733) * p(m, 1741)s15 = p(m, 1747) * p(m, 1753) * p(m, 1759) * p(m, 1777) * p(m, 1783) * p(m, 1787) * p(m, 1789) * p(m, 1801) * p(m, 1811) * p(m, 1823) * p(m, 1831) * p(m, 1847) * p(m, 1861) * p(m, 1867) * p(m, 1871) * p(m, 1873) * p(m, 1877)s16 = p(m, 1879) * p(m, 1889) * p(m, 1901) * p(m, 1907) * p(m, 1913) * p(m, 1931) * p(m, 1933) * p(m, 1949) * p(m, 1951) * p(m, 1973) * p(m, 1979) * p(m, 1987) * p(m, 1993) * p(m, 1997) * p(m, 1999) * p(m, 2003) * p(m, 2011)s17 = p(m, 2017) * p(m, 2027) * p(m, 2029) * p(m, 2039) * p(m, 2053) * p(m, 2063) * p(m, 2069) * p(m, 2081) * p(m, 2083) * p(m, 2087) * p(m, 2089) * p(m, 2099) * p(m, 2111) * p(m, 2113) * p(m, 2129) * p(m, 2131) * p(m, 2137)s18 = p(m, 2141) * p(m, 2143) * p(m, 2153) * p(m, 2161) * p(m, 2179) * p(m, 2203) * p(m, 2207) * p(m, 2213) * p(m, 2221) * p(m, 2237) * p(m, 2239) * p(m, 2243) * p(m, 2251) * p(m, 2267) * p(m, 2269) * p(m, 2273) * p(m, 2281)s19 = p(m, 2287) * p(m, 2293) * p(m, 2297) * p(m, 2309) * p(m, 2311) * p(m, 2333) * p(m, 2339) * p(m, 2341) * p(m, 2347) * p(m, 2351) * p(m, 2357) * p(m, 2371) * p(m, 2377) * p(m, 2381) * p(m, 2383) * p(m, 2389) * p(m, 2393)s20 = p(m, 2399) * p(m, 2411) * p(m, 2417) * p(m, 2423) * p(m, 2437) * p(m, 2441) * p(m, 2447) * p(m, 2459) * p(m, 2467) * p(m, 2473) * p(m, 2477) * p(m, 2503) * p(m, 2521) * p(m, 2531) * p(m, 2539) * p(m, 2543) * p(m, 2549)s21 = p(m, 2551) * p(m, 2557) * p(m, 2579) * p(m, 2591) * p(m, 2593) * p(m, 2609) * p(m, 2617) * p(m, 2621) * p(m, 2633) * p(m, 2647) * p(m, 2657) * p(m, 2659) * p(m, 2663) * p(m, 2671) * p(m, 2677) * p(m, 2683) * p(m, 2687)s22 = p(m, 2689) * p(m, 2693) * p(m, 2699) * p(m, 2707) * p(m, 2711) * p(m, 2713) * p(m, 2719) * p(m, 2729) * p(m, 2731) * p(m, 2741) * p(m, 2749) * p(m, 2753) * p(m, 2767) * p(m, 2777) * p(m, 2789) * p(m, 2791) * p(m, 2797)s23 = p(m, 2801) * p(m, 2803) * p(m, 2819) * p(m, 2833) * p(m, 2837) * p(m, 2843) * p(m, 2851) * p(m, 2857) * p(m, 2861) * p(m, 2879) * p(m, 2887) * p(m, 2897) * p(m, 2903) * p(m, 2909) * p(m, 2917) * p(m, 2927) * p(m, 2939)s24 = p(m, 2953) * p(m, 2957) * p(m, 2963) * p(m, 2969) * p(m, 2971) * p(m, 2999) * p(m, 3001) * p(m, 3011) * p(m, 3019) * p(m, 3023) * p(m, 3037) * p(m, 3041) * p(m, 3049) * p(m, 3061) * p(m, 3067) * p(m, 3079) * p(m, 3083)qp = s * s1 * s2 * s3 * s4 * s5 * s6 * s7 * s8 * s9 * s10 * s11 * s12 * s13 * s14 * s15 * s16 * s17 * s18 * s19 * s20 * s21 * s22 * s23 * s24End Function此程序还需改进。

集合实现筛选法求素数素数在数学领域中有着重要的地位，不仅在数学本身中拥有广泛的应用，而且在计算机科学中也具有重要的意义。

我们知道，素数指的是只能被1和它本身整除的数，那么如何求解素数？一般来说，我们可以使用试除法或者埃拉托色尼筛法等方法来求解素数。

而今天我们要介绍的是集合实现筛选法求素数。

1. 筛选法的基本原理筛选法求素数的基本原理是通过枚举法把小于等于N的合数筛去，最后剩下的就是质数。

具体而言，我们可以定义一个长度为N的数组来表示1~N这些数的是否为质数的状态，然后通过遍历数组并对其状态进行处理来找出所有的素数。

具体实现方法可以分为两类，分别是埃氏筛法和欧拉筛法。

2. 埃氏筛法埃氏筛法的核心思想是，对于一个素数p，可以将小于等于N 中可以被p整除的数全部排除掉。

例如，对于素数2，我们需要把4、6、8……都去掉，再对素数3进行筛选时，需要去掉9、12、15……以此类推。

实现时，我们可以先定义一个长度为N的bool类型数组，每个元素默认为true。

然后从2开始枚举每个数，如果该数为素数，则将其倍数全部筛除。

具体代码如下：bool isPrime[10001]; // 用于标记素数状态void eratosthenes(int n) {memset(isPrime, true, sizeof(isPrime)); // 初始化全部为素数for (int i = 2; i * i <= n; i++) {if (isPrime[i]) {for (int j = i * 2; j <= n; j += i) { // 筛除素数i的所有倍数 isPrime[j] = false;}}}}3. 欧拉筛法欧拉筛法和埃氏筛法原理类似，但是有一些优化策略，可以大大提升算法效率。

首先，我们仍然需要定义一个长度为N的bool类型数组来标记素数状态，但是这里我们将其作为一个集合来操作。

具体而言，在进行筛选时，我们使用一个数组primes来记录当前已知的素数，然后针对每个数n，依次将其与primes中的每个素数进行比较。