给定限制,打印小于或等于给定限制的所有素数。
例如:
Input: limit = 10Output: 2, 3, 5, 7Input: limit = 20Output: 2, 3, 5, 7, 11, 13, 17, 19
我们在下面讨论了上述任务的算法。 埃拉托斯坦筛 圣代拉姆筛 Atkin的筛是一种现代算法,用于查找指定整数以下的所有素数。与古代相比 埃拉托斯坦筛 ,它标记出素数的倍数,它做了一些准备工作,然后标记出素数平方的倍数,这就是为什么它具有更好的理论渐近复杂性 (N/(logn))的复杂性
算法:
- 创建一个结果列表,填入2、3和5。
- 为每个正整数创建一个筛选列表;此列表中的所有条目最初应标记为非素数。
- 对于筛子列表中的每个条目编号n,模60余数r:
- 如果r为1、13、17、29、37、41、49或53,则将每个可能解决方案的条目翻转为4x 2. +y 2. =n。
- 如果r为7、19、31或43,则将每个可能的解决方案的条目翻转为3倍 2. +y 2. =n。
- 如果r为11、23、47或59,则将每个可能的解决方案的条目翻转为3倍 2. –y 2. 当x>y时=n。
- 如果r是其他东西,完全忽略它…
- 从筛子列表中的最低数字开始。
- 在筛子列表中取下一个数字,仍然标记为素数。
- 将数字包括在结果列表中。
- 将数字平方,并将该平方的所有倍数标记为非素数。请注意,可以被2、3或5分解的倍数不需要标记,因为在素数的最终枚举中,这些倍数将被忽略。
- 重复第四步到第七步。
下面是上述算法的实现。
C++
// C++ program for implementation of Sieve of Atkin #include <bits/stdc++.h> using namespace std; int SieveOfAtkin( int limit) { // 2 and 3 are known to be prime if (limit > 2) cout << 2 << " " ; if (limit > 3) cout << 3 << " " ; // Initialise the sieve array with false values bool sieve[limit]; for ( int i = 0; i < limit; i++) sieve[i] = false ; /* Mark sieve[n] is true if one of the following is true: a) n = (4*x*x)+(y*y) has odd number of solutions, i.e., there exist odd number of distinct pairs (x, y) that satisfy the equation and n % 12 = 1 or n % 12 = 5. b) n = (3*x*x)+(y*y) has odd number of solutions and n % 12 = 7 c) n = (3*x*x)-(y*y) has odd number of solutions, x > y and n % 12 = 11 */ for ( int x = 1; x * x < limit; x++) { for ( int y = 1; y * y < limit; y++) { // Main part of Sieve of Atkin int n = (4 * x * x) + (y * y); if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true ; n = (3 * x * x) + (y * y); if (n <= limit && n % 12 == 7) sieve[n] ^= true ; n = (3 * x * x) - (y * y); if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true ; } } // Mark all multiples of squares as non-prime for ( int r = 5; r * r < limit; r++) { if (sieve[r]) { for ( int i = r * r; i < limit; i += r * r) sieve[i] = false ; } } // Print primes using sieve[] for ( int a = 5; a < limit; a++) if (sieve[a]) cout << a << " " ; } // Driver program int main( void ) { int limit = 20; SieveOfAtkin(limit); return 0; } |
JAVA
// Java program for implementation of Sieve // of Atkin class GFG { static int SieveOfAtkin( int limit) { // 2 and 3 are known to be prime if (limit > 2 ) System.out.print( 2 + " " ); if (limit > 3 ) System.out.print( 3 + " " ); // Initialise the sieve array with // false values boolean sieve[] = new boolean [limit]; for ( int i = 0 ; i < limit; i++) sieve[i] = false ; /* Mark sieve[n] is true if one of the following is true: a) n = (4*x*x)+(y*y) has odd number of solutions, i.e., there exist odd number of distinct pairs (x, y) that satisfy the equation and n % 12 = 1 or n % 12 = 5. b) n = (3*x*x)+(y*y) has odd number of solutions and n % 12 = 7 c) n = (3*x*x)-(y*y) has odd number of solutions, x > y and n % 12 = 11 */ for ( int x = 1 ; x * x < limit; x++) { for ( int y = 1 ; y * y < limit; y++) { // Main part of Sieve of Atkin int n = ( 4 * x * x) + (y * y); if (n <= limit && (n % 12 == 1 || n % 12 == 5 )) sieve[n] ^= true ; n = ( 3 * x * x) + (y * y); if (n <= limit && n % 12 == 7 ) sieve[n] ^= true ; n = ( 3 * x * x) - (y * y); if (x > y && n <= limit && n % 12 == 11 ) sieve[n] ^= true ; } } // Mark all multiples of squares as // non-prime for ( int r = 5 ; r * r < limit; r++) { if (sieve[r]) { for ( int i = r * r; i < limit; i += r * r) sieve[i] = false ; } } // Print primes using sieve[] for ( int a = 5 ; a < limit; a++) if (sieve[a]) System.out.print(a + " " ); return 0 ; } // Driver code public static void main(String[] args) { int limit = 20 ; SieveOfAtkin(limit); } } // This code is contributed by Anant Agarwal. |
Python 3
# Python 3 program for # implementation of # Sieve of Atkin def SieveOfAtkin(limit): # 2 and 3 are known # to be prime if limit > 2 : print ( 2 , end = " " ) if limit > 3 : print ( 3 , end = " " ) # Initialise the sieve # array with False values sieve = [ False ] * limit for i in range ( 0 , limit): sieve[i] = False '''Mark sieve[n] is True if one of the following is True: a) n = (4*x*x)+(y*y) has odd number of solutions, i.e., there exist odd number of distinct pairs (x, y) that satisfy the equation and n % 12 = 1 or n % 12 = 5. b) n = (3*x*x)+(y*y) has odd number of solutions and n % 12 = 7 c) n = (3*x*x)-(y*y) has odd number of solutions, x > y and n % 12 = 11 ''' x = 1 while x * x < limit: y = 1 while y * y < limit: # Main part of # Sieve of Atkin n = ( 4 * x * x) + (y * y) if (n < = limit and (n % 12 = = 1 or n % 12 = = 5 )): sieve[n] ^ = True n = ( 3 * x * x) + (y * y) if n < = limit and n % 12 = = 7 : sieve[n] ^ = True n = ( 3 * x * x) - (y * y) if (x > y and n < = limit and n % 12 = = 11 ): sieve[n] ^ = True y + = 1 x + = 1 # Mark all multiples of # squares as non-prime r = 5 while r * r < limit: if sieve[r]: for i in range (r * r, limit, r * r): sieve[i] = False r + = 1 # Print primes # using sieve[] for a in range ( 5 , limit): if sieve[a]: print (a, end = " " ) # Driver Code limit = 20 SieveOfAtkin(limit) # This code is contributed # by Smitha |
C#
// C# program for implementation of Sieve // of Atkin using System; class GFG { static int SieveOfAtkin( int limit) { // 2 and 3 are known to be prime if (limit > 2) Console.Write(2 + " " ); if (limit > 3) Console.Write(3 + " " ); // Initialise the sieve array with // false values bool [] sieve = new bool [limit]; for ( int i = 0; i < limit; i++) sieve[i] = false ; /* Mark sieve[n] is true if one of the following is true: a) n = (4*x*x)+(y*y) has odd number of solutions, i.e., there exist odd number of distinct pairs (x, y) that satisfy the equation and n % 12 = 1 or n % 12 = 5. b) n = (3*x*x)+(y*y) has odd number of solutions and n % 12 = 7 c) n = (3*x*x)-(y*y) has odd number of solutions, x > y and n % 12 = 11 */ for ( int x = 1; x * x < limit; x++) { for ( int y = 1; y * y < limit; y++) { // Main part of Sieve of Atkin int n = (4 * x * x) + (y * y); if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true ; n = (3 * x * x) + (y * y); if (n <= limit && n % 12 == 7) sieve[n] ^= true ; n = (3 * x * x) - (y * y); if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true ; } } // Mark all multiples of squares as // non-prime for ( int r = 5; r * r < limit; r++) { if (sieve[r]) { for ( int i = r * r; i < limit; i += r * r) sieve[i] = false ; } } // Print primes using sieve[] for ( int a = 5; a < limit; a++) if (sieve[a]) Console.Write(a + " " ); return 0; } // Driver code public static void Main() { int limit = 20; SieveOfAtkin(limit); } } // This code is contributed by nitin mittal |
PHP
<?php // PHP program for implementation // of Sieve of Atkin function SieveOfAtkin( $limit ) { // 2 and 3 are known // to be prime if ( $limit > 2) echo 2 , " " ; if ( $limit > 3) echo 3 , " " ; // Initialise the sieve array // with false values $sieve [ $limit ] = 0; for ( $i = 0; $i < $limit ; $i ++) $sieve [ $i ] = false; /* Mark sieve[n] is true if one of the following is true: a) n = (4*x*x)+(y*y) has odd number of solutions, i.e., there exist odd number of distinct pairs (x, y) that satisfy the equation and n % 12 = 1 or n % 12 = 5. b) n = (3*x*x)+(y*y) has odd number of solutions and n % 12 = 7 c) n = (3*x*x)-(y*y) has odd number of solutions, x > y and n % 12 = 11 */ for ( $x = 1; $x * $x < $limit ; $x ++) { for ( $y = 1; $y * $y < $limit ; $y ++) { // Main part of Sieve of Atkin $n = (4 * $x * $x ) + ( $y * $y ); if ( $n <= $limit && ( $n % 12 == 1 || $n % 12 == 5)) $sieve [ $n ] ^= true; $n = (3 * $x * $x ) + ( $y * $y ); if ( $n <= $limit && $n % 12 == 7) $sieve [ $n ] = true; $n = (3 * $x * $x ) - ( $y * $y ); if ( $x > $y && $n <= $limit && $n % 12 == 11) $sieve [ $n ] ^= true; } } // Mark all multiples of // squares as non-prime for ( $r = 5; $r * $r < $limit ; $r ++) { if ( $sieve [ $r ]) { for ( $i = $r * $r ; $i < $limit ; $i += $r * $r ) $sieve [ $i ] = false; } } // Print primes // using sieve[] for ( $a = 5; $a < $limit ; $a ++) if ( $sieve [ $a ]) echo $a , " " ; } // Driver Code $limit = 20; SieveOfAtkin( $limit ); // This code is contributed by nitin mittal. ?> |
Javascript
<script> // Javascript program for implementation // of Sieve of Atkin function SieveOfAtkin(limit) { // 2 and 3 are known // to be prime if (limit > 2) document.write(2 + " " ); if (limit > 3) document.write(3 + " " ); // Initialise the sieve array // with false values let sieve = new Array() sieve[limit] = 0; for (let i = 0; i < limit; i++) sieve[i] = false ; /* Mark sieve[n] is true if one of the following is true: a) n = (4*x*x)+(y*y) has odd number of solutions, i.e., there exist odd number of distinct pairs (x, y) that satisfy the equation and n % 12 = 1 or n % 12 = 5. b) n = (3*x*x)+(y*y) has odd number of solutions and n % 12 = 7 c) n = (3*x*x)-(y*y) has odd number of solutions, x > y and n % 12 = 11 */ for (let x = 1; x * x < limit; x++) { for (let y = 1; y * y < limit; y++) { // Main part of Sieve of Atkin let n = (4 * x * x) + (y * y); if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true ; n = (3 * x * x) + (y * y); if (n <= limit && n % 12 == 7) sieve[n] = true ; n = (3 * x * x) - (y * y); if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true ; } } // Mark all multiples of // squares as non-prime for (let r = 5; r * r < limit; r++) { if (sieve[r]) { for (i = r * r; i < limit; i += r * r) sieve[i] = false ; } } // Print primes // using sieve[] for (let a = 5; a < limit; a++) if (sieve[a]) document.write(a , " " ); } // Driver Code let limit = 20; SieveOfAtkin(limit); // This code is contributed by nitin gfgking </script> |
输出:
2 3 5 7 11 13 17 19
工作原理:
- 该算法将2、3和5视为特殊情况,只需将它们添加到素数集中即可。
- 就像埃拉托斯坦筛一样,我们从一系列我们想要调查的数字开始。假设我们想要找到<=100的素数,那么我们为[5100]列一个列表。如(1)所述,2、3和5是特例,4不是素数。
- 该算法是以模60余数表示的…
- 所有具有模六十余数1、13、17、29、37、41、49或53的数字都具有模十二余数1或5。当且仅当4×2+y2=n的解的个数为奇数且无平方时,这些数为素数。无平方整数是不能被除1以外的任何完美平方整除的整数。
- 所有模60余数为7、19、31或43的数字的模6余数均为1。当且仅当解的个数为3x时,这些数是素数 2. +y 2. =n为奇数,且该数为无平方。
- 所有模60余数为11、23、47或59的数字都有模12余数11。当且仅当解的个数为3x时,这些数是素数 2. –y 2. =n为奇数,且该数为无平方。
让我们看看它是如何生成最多20个素数的:
1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 20
第0步: 开头的所有数字的状态都为false。特殊的数字是2、3和5,它们被称为素数。
第一步: 为条件生成值。
第二步: 根据条件翻转状态。 在x,y循环中生成的表中的上述n值将在模条件下进行测试。 第1栏: 如果(列1值)%12==1或5 然后翻转该数字的筛选状态。 我们用12代替60。这是因为如果我们取模60,那么我们必须考虑R等于1, 13, 17、29, 37, 41、49或53,而对于所有这些R,MOD 12是1或5。(仅用于减小表达式大小) 第2栏: 如果(列2值)%12==7 然后翻转该数字的筛选状态。 第3栏: 如果(列3值)%12==11 然后翻转该数字的筛选状态。
第三步: 检查无平方条件:如果列表中的任何数字是任何数字的平方,则将其删除。
第4步: 创建状态为真的素数数组。 i、 e.2 3 5 7 11 13 17 19
第5步: 在屏幕上打印输出。 本文由 Anuj Rathore 。如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请发表评论。