Eratosthenes筛的Python程序-yiteyi-C++库

Eratosthenes筛是一种寻找所有达到（可能包括）给定自然值的素数的方法。当自然数相对较小时，这种方法效果良好，允许我们确定任何小于或等于的自然数是素数还是复合数。

null

给定一个数字n，打印出所有小于或等于n的素数。同时也给出n是一个小数字。例如，如果n为10，则输出应为“2、3、5、7”。如果n为20，则输出应为“2、3、5、7、11、13、17、19”。

Python3

                         ''' Python program to print all primes smaller than or equal to                       
                                                 n using Sieve of Eratosthenes'''                       
           
                         def                                     SieveOfEratosthenes(n):                       
                                   
                                                 '''Create a boolean array "prime[0..n]" and initialize                       
                                                 all entries it as true. A value in prime[i] will                       
                                                 finally be false if i is Not a prime, else true.'''                       
                                                 prime                                     =                                     [                                     True                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                                 p                                     =                                     2                       
                                                 while                                     (p                                     *                                     p <                                     =                                     n):                       
                                   
                                                 # If prime[p] is not changed, then it is a prime                       
                                                 if                                     (prime[p]                                     =                                     =                                     True                                     ):                       
                                   
                                                 # Update all multiples of p                       
                                                 for                                     i                                     in                                     range                                     (p                                     *                                     *                                     2                                     , n                                     +                                     1                                     , p):                       
                                                 prime[i]                                     =                                     False                       
                                                 p                                     +                                     =                                     1                       
                                                 prime[                                     0                                     ]                                     =                                     False                       
                                                 prime[                                     1                                     ]                                     =                                     False                       
                                                 # Print all prime numbers                       
                                                 for                                     p                                     in                                     range                                     (n                                     +                                     1                                     ):                       
                                                 if                                     prime[p]:                       
                                                 print                                     (p,end                                     =                                     ' '                                     )                                     #Use print(p) for python 3                       
           
                         # driver program                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 n                                     =                                     30                       
                                                 print                                     (                                     "Following are the prime numbers smaller"                                     , end                                     =                                     ' '                                     )                       
                                                 #Use print("Following are the prime numbers smaller") for Python 3                       
                                                 print                                     (                                     "than or equal to"                                     , n)                       
                                                 #Use print("than or equal to", n) for Python 3                       
                                                 SieveOfEratosthenes(n)                       

输出：

Following are the prime numbers below 302 3 5 7 11 13 17 19 23 29

请参阅完整的文章埃拉托斯坦筛更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章