阿特金筛

给定限制,打印小于或等于给定限制的所有素数。

null

例如:

Input:  limit = 10Output: 2, 3, 5, 7Input:  limit = 20Output: 2, 3, 5, 7, 11, 13, 17, 19 

我们在下面讨论了上述任务的算法。 埃拉托斯坦筛 圣代拉姆筛 Atkin的筛是一种现代算法,用于查找指定整数以下的所有素数。与古代相比 埃拉托斯坦筛 ,它标记出素数的倍数,它做了一些准备工作,然后标记出素数平方的倍数,这就是为什么它具有更好的理论渐近复杂性 (N/(logn))的复杂性

算法:

  1. 创建一个结果列表,填入2、3和5。
  2. 为每个正整数创建一个筛选列表;此列表中的所有条目最初应标记为非素数。
  3. 对于筛子列表中的每个条目编号n,模60余数r:
    1. 如果r为1、13、17、29、37、41、49或53,则将每个可能解决方案的条目翻转为4x 2. +y 2. =n。
    2. 如果r为7、19、31或43,则将每个可能的解决方案的条目翻转为3倍 2. +y 2. =n。
    3. 如果r为11、23、47或59,则将每个可能的解决方案的条目翻转为3倍 2. –y 2. 当x>y时=n。
    4. 如果r是其他东西,完全忽略它…
  4. 从筛子列表中的最低数字开始。
  5. 在筛子列表中取下一个数字,仍然标记为素数。
  6. 将数字包括在结果列表中。
  7. 将数字平方,并将该平方的所有倍数标记为非素数。请注意,可以被2、3或5分解的倍数不需要标记,因为在素数的最终枚举中,这些倍数将被忽略。
  8. 重复第四步到第七步。

下面是上述算法的实现。

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 

工作原理:

  1. 该算法将2、3和5视为特殊情况,只需将它们添加到素数集中即可。
  2. 就像埃拉托斯坦筛一样,我们从一系列我们想要调查的数字开始。假设我们想要找到<=100的素数,那么我们为[5100]列一个列表。如(1)所述,2、3和5是特例,4不是素数。
  3. 该算法是以模60余数表示的…
  4. 所有具有模六十余数1、13、17、29、37、41、49或53的数字都具有模十二余数1或5。当且仅当4×2+y2=n的解的个数为奇数且无平方时,这些数为素数。无平方整数是不能被除1以外的任何完美平方整除的整数。
  5. 所有模60余数为7、19、31或43的数字的模6余数均为1。当且仅当解的个数为3x时,这些数是素数 2. +y 2. =n为奇数,且该数为无平方。
  6. 所有模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,它们被称为素数。

第一步: 为条件生成值。

atkins

第二步: 根据条件翻转状态。 在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 。如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请发表评论。

© 版权声明
THE END
喜欢就支持一下吧
点赞12 分享