给定一个数字n，打印所有小于n的素数。例如，如果给定的数字是10，则输出2、3、5、7。
null
一种简单的方法是运行一个从0到n-1的循环，并检查每个数字的素数。更好的方法是使用 埃拉托斯烯的简单筛 .
C
// This functions finds all primes smaller than 'limit' // using simple sieve of eratosthenes. void simpleSieve( int limit) { // Create a boolean array "mark[0..limit-1]" and // initialize all entries of it as true. A value // in mark[p] will finally be false if 'p' is Not // a prime, else true. bool mark[limit]; for ( int i = 0; i<limit; i++) { mark[i] = true ; } // One by one traverse all numbers so that their // multiples can be marked as composite. for ( int p=2; p*p<limit; p++) { // If p is not changed, then it is a prime if (mark[p] == true ) { // Update all multiples of p for ( int i=p*p; i<limit; i+=p) mark[i] = false ; } } // Print all prime numbers and store them in prime for ( int p=2; p<limit; p++) if (mark[p] == true ) cout << p << " " ; } |
JAVA
// This functions finds all primes smaller than 'limit' // using simple sieve of eratosthenes. static void simpleSieve( int limit) { // Create a boolean array "mark[0..limit-1]" and // initialize all entries of it as true. A value // in mark[p] will finally be false if 'p' is Not // a prime, else true. boolean []mark = new boolean [limit]; Arrays.fill(mark, true ); // One by one traverse all numbers so that their // multiples can be marked as composite. for ( int p = 2 ; p * p < limit; p++) { // If p is not changed, then it is a prime if (mark[p] == true ) { // Update all multiples of p for ( int i = p * p; i < limit; i += p) mark[i] = false ; } } // Print all prime numbers and store them in prime for ( int p = 2 ; p < limit; p++) if (mark[p] == true ) System.out.print(p + " " ); } // This code is contributed by rutvik_56. |
Python3
# This functions finds all primes smaller than 'limit' # using simple sieve of eratosthenes. def simpleSieve(limit): # Create a boolean array "mark[0..limit-1]" and # initialize all entries of it as true. A value # in mark[p] will finally be false if 'p' is Not # a prime, else true. mark = [ True for i in range (limit)] # One by one traverse all numbers so that their # multiples can be marked as composite. for p in range (p * p, limit - 1 , 1 ): # If p is not changed, then it is a prime if (mark[p] = = True ): # Update all multiples of p for i in range (p * p, limit - 1 , p): mark[i] = False # Print all prime numbers and store them in prime for p in range ( 2 , limit - 1 , 1 ): if (mark[p] = = True ): print (p, end = " " ) # This code is contributed by Dharanendra L V. |
C#
// This functions finds all primes smaller than 'limit' // using simple sieve of eratosthenes. static void simpleSieve( int limit) { // Create a boolean array "mark[0..limit-1]" and // initialize all entries of it as true. A value // in mark[p] will finally be false if 'p' is Not // a prime, else true. bool []mark = new bool [limit]; Array.Fill(mark, true ); // One by one traverse all numbers so that their // multiples can be marked as composite. for ( int p = 2; p * p < limit; p++) { // If p is not changed, then it is a prime if (mark[p] == true ) { // Update all multiples of p for ( int i = p * p; i < limit; i += p) mark[i] = false ; } } // Print all prime numbers and store them in prime for ( int p = 2; p < limit; p++) if (mark[p] == true ) Console.Write(p + " " ); } // This code is contributed by pratham76. |
Javascript
<script> // This functions finds all primes smaller than 'limit' // using simple sieve of eratosthenes. function simpleSieve(limit) { // Create a boolean array "mark[0..limit-1]" and // initialize all entries of it as true. A value // in mark[p] will finally be false if 'p' is Not // a prime, else true. var mark = Array(limit).fill( true ); // One by one traverse all numbers so that their // multiples can be marked as composite. for (p = 2; p * p < limit; p++) { // If p is not changed, then it is a prime if (mark[p] == true ) { // Update all multiples of p for (i = p * p; i < limit; i += p) mark[i] = false ; } } // Print all prime numbers and store them in prime for (p = 2; p < limit; p++) if (mark[p] == true ) document.write(p + " " ); } // This code is contributed by todaysgaurav </script> |
简单筛子的问题： 埃拉托色尼的筛子看起来不错，但是考虑到当N很大时，简单筛就面临下列问题。
- 大小为Θ（n）的数组可能不适合内存
- 简单筛子即使对于稍大的n也不适合缓存。该算法遍历数组时没有引用的局部性
分段筛 分段筛的概念是将[0..n-1]范围划分为不同的段，并逐个计算所有段中的素数。该算法首先使用简单的筛子来寻找小于或等于√（n） 。下面是分段筛网中使用的步骤。
- 使用简单的筛子找到所有的素数，直到’n’的平方根，并将这些素数存储在一个数组“prime[]”中。将找到的素数存储在数组“prime[]”中。
- 我们需要[0..n-1]范围内的所有素数。我们将这个范围划分为不同的部分，这样每个部分的大小最多为√N
- 对每段进行以下操作[低..高]
- 创建一个数组标记[high-low+1]。这里我们只需要O（x）空间 十、 是给定范围内的多个元素。
- 遍历步骤1中找到的所有素数。对于每个素数，标记其在给定范围内的倍数[低..高]。
在简单筛中，我们需要O（n）空间，这对于大n可能不可行(√n） 空间，我们一次处理较小的范围（参考位置）
下面是上述想法的实施。
C++
// C++ program to print print all primes smaller than // n using segmented sieve #include <bits/stdc++.h> using namespace std; // This functions finds all primes smaller than 'limit' // using simple sieve of eratosthenes. It also stores // found primes in vector prime[] void simpleSieve( int limit, vector< int > &prime) { // Create a boolean array "mark[0..n-1]" and initialize // all entries of it as true. A value in mark[p] will // finally be false if 'p' is Not a prime, else true. vector< bool > mark(limit + 1, true ); for ( int p=2; p*p<limit; p++) { // If p is not changed, then it is a prime if (mark[p] == true ) { // Update all multiples of p for ( int i=p*p; i<limit; i+=p) mark[i] = false ; } } // Print all prime numbers and store them in prime for ( int p=2; p<limit; p++) { if (mark[p] == true ) { prime.push_back(p); cout << p << " " ; } } } // Prints all prime numbers smaller than 'n' void segmentedSieve( int n) { // Compute all primes smaller than or equal // to square root of n using simple sieve int limit = floor ( sqrt (n))+1; vector< int > prime; prime.reserve(limit); simpleSieve(limit, prime); // Divide the range [0..n-1] in different segments // We have chosen segment size as sqrt(n). int low = limit; int high = 2*limit; // While all segments of range [0..n-1] are not processed, // process one segment at a time while (low < n) { if (high >= n) high = n; // To mark primes in current range. A value in mark[i] // will finally be false if 'i-low' is Not a prime, // else true. bool mark[limit+1]; memset (mark, true , sizeof (mark)); // Use the found primes by simpleSieve() to find // primes in current range for ( int i = 0; i < prime.size(); i++) { // Find the minimum number in [low..high] that is // a multiple of prime[i] (divisible by prime[i]) // For example, if low is 31 and prime[i] is 3, // we start with 33. int loLim = floor (low/prime[i]) * prime[i]; if (loLim < low) loLim += prime[i]; /* Mark multiples of prime[i] in [low..high]: We are marking j - low for j, i.e. each number in range [low, high] is mapped to [0, high-low] so if range is [50, 100] marking 50 corresponds to marking 0, marking 51 corresponds to 1 and so on. In this way we need to allocate space only for range */ for ( int j=loLim; j<high; j+=prime[i]) mark[j-low] = false ; } // Numbers which are not marked as false are prime for ( int i = low; i<high; i++) if (mark[i - low] == true ) cout << i << " " ; // Update low and high for next segment low = low + limit; high = high + limit; } } // Driver program to test above function int main() { int n = 100000; cout << "Primes smaller than " << n << ":n" ; segmentedSieve(n); return 0; } |
JAVA
// Java program to print print all primes smaller than // n using segmented sieve import java.util.Vector; import static java.lang.Math.sqrt; import static java.lang.Math.floor; class Test { // This methid finds all primes smaller than 'limit' // using simple sieve of eratosthenes. It also stores // found primes in vector prime[] static void simpleSieve( int limit, Vector<Integer> prime) { // Create a boolean array "mark[0..n-1]" and initialize // all entries of it as true. A value in mark[p] will // finally be false if 'p' is Not a prime, else true. boolean mark[] = new boolean [limit+ 1 ]; for ( int i = 0 ; i < mark.length; i++) mark[i] = true ; for ( int p= 2 ; p*p<limit; p++) { // If p is not changed, then it is a prime if (mark[p] == true ) { // Update all multiples of p for ( int i=p*p; i<limit; i+=p) mark[i] = false ; } } // Print all prime numbers and store them in prime for ( int p= 2 ; p<limit; p++) { if (mark[p] == true ) { prime.add(p); System.out.print(p + " " ); } } } // Prints all prime numbers smaller than 'n' static void segmentedSieve( int n) { // Compute all primes smaller than or equal // to square root of n using simple sieve int limit = ( int ) (floor(sqrt(n))+ 1 ); Vector<Integer> prime = new Vector<>(); simpleSieve(limit, prime); // Divide the range [0..n-1] in different segments // We have chosen segment size as sqrt(n). int low = limit; int high = 2 *limit; // While all segments of range [0..n-1] are not processed, // process one segment at a time while (low < n) { if (high >= n) high = n; // To mark primes in current range. A value in mark[i] // will finally be false if 'i-low' is Not a prime, // else true. boolean mark[] = new boolean [limit+ 1 ]; for ( int i = 0 ; i < mark.length; i++) mark[i] = true ; // Use the found primes by simpleSieve() to find // primes in current range for ( int i = 0 ; i < prime.size(); i++) { // Find the minimum number in [low..high] that is // a multiple of prime.get(i) (divisible by prime.get(i)) // For example, if low is 31 and prime.get(i) is 3, // we start with 33. int loLim = ( int ) (floor(low/prime.get(i)) * prime.get(i)); if (loLim < low) loLim += prime.get(i); /* Mark multiples of prime.get(i) in [low..high]: We are marking j - low for j, i.e. each number in range [low, high] is mapped to [0, high-low] so if range is [50, 100] marking 50 corresponds to marking 0, marking 51 corresponds to 1 and so on. In this way we need to allocate space only for range */ for ( int j=loLim; j<high; j+=prime.get(i)) mark[j-low] = false ; } // Numbers which are not marked as false are prime for ( int i = low; i<high; i++) if (mark[i - low] == true ) System.out.print(i + " " ); // Update low and high for next segment low = low + limit; high = high + limit; } } // Driver method public static void main(String args[]) { int n = 100 ; System.out.println( "Primes smaller than " + n + ":" ); segmentedSieve(n); } } |
Python3
# Python3 program to print all primes # smaller than n, using segmented sieve import math prime = [] # This method finds all primes # smaller than 'limit' using # simple sieve of eratosthenes. # It also stores found primes in list prime def simpleSieve(limit): # Create a boolean list "mark[0..n-1]" and # initialize all entries of it as True. # A value in mark[p] will finally be False # if 'p' is Not a prime, else True. mark = [ True for i in range (limit + 1 )] p = 2 while (p * p < = limit): # If p is not changed, then it is a prime if (mark[p] = = True ): # Update all multiples of p for i in range (p * p, limit + 1 , p): mark[i] = False p + = 1 # Print all prime numbers # and store them in prime for p in range ( 2 , limit): if mark[p]: prime.append(p) print (p,end = " " ) # Prints all prime numbers smaller than 'n' def segmentedSieve(n): # Compute all primes smaller than or equal # to square root of n using simple sieve limit = int (math.floor(math.sqrt(n)) + 1 ) simpleSieve(limit) # Divide the range [0..n-1] in different segments # We have chosen segment size as sqrt(n). low = limit high = limit * 2 # While all segments of range [0..n-1] are not processed, # process one segment at a time while low < n: if high > = n: high = n # To mark primes in current range. A value in mark[i] # will finally be False if 'i-low' is Not a prime, # else True. mark = [ True for i in range (limit + 1 )] # Use the found primes by simpleSieve() # to find primes in current range for i in range ( len (prime)): # Find the minimum number in [low..high] # that is a multiple of prime[i] # (divisible by prime[i]) # For example, if low is 31 and prime[i] is 3, # we start with 33. loLim = int (math.floor(low / prime[i]) * prime[i]) if loLim < low: loLim + = prime[i] # Mark multiples of prime[i] in [low..high]: # We are marking j - low for j, i.e. each number # in range [low, high] is mapped to [0, high-low] # so if range is [50, 100] marking 50 corresponds # to marking 0, marking 51 corresponds to 1 and # so on. In this way we need to allocate space # only for range for j in range (loLim, high, prime[i]): mark[j - low] = False # Numbers which are not marked as False are prime for i in range (low, high): if mark[i - low]: print (i, end = " " ) # Update low and high for next segment low = low + limit high = high + limit # Driver Code n = 100 print ( "Primes smaller than" , n, ":" ) segmentedSieve( 100 ) # This code is contributed by bhavyadeep |
C#
// C# program to print print // all primes smaller than // n using segmented sieve using System; using System.Collections; class GFG { // This methid finds all primes // smaller than 'limit' using simple // sieve of eratosthenes. It also stores // found primes in vector prime[] static void simpleSieve( int limit, ArrayList prime) { // Create a boolean array "mark[0..n-1]" // and initialize all entries of it as // true. A value in mark[p] will finally be // false if 'p' is Not a prime, else true. bool [] mark = new bool [limit + 1]; for ( int i = 0; i < mark.Length; i++) mark[i] = true ; for ( int p = 2; p * p < limit; p++) { // If p is not changed, then it is a prime if (mark[p] == true ) { // Update all multiples of p for ( int i = p * p; i < limit; i += p) mark[i] = false ; } } // Print all prime numbers and store them in prime for ( int p = 2; p < limit; p++) { if (mark[p] == true ) { prime.Add(p); Console.Write(p + " " ); } } } // Prints all prime numbers smaller than 'n' static void segmentedSieve( int n) { // Compute all primes smaller than or equal // to square root of n using simple sieve int limit = ( int ) (Math.Floor(Math.Sqrt(n)) + 1); ArrayList prime = new ArrayList(); simpleSieve(limit, prime); // Divide the range [0..n-1] in // different segments We have chosen // segment size as sqrt(n). int low = limit; int high = 2*limit; // While all segments of range // [0..n-1] are not processed, // process one segment at a time while (low < n) { if (high >= n) high = n; // To mark primes in current range. // A value in mark[i] will finally // be false if 'i-low' is Not a prime, // else true. bool [] mark = new bool [limit + 1]; for ( int i = 0; i < mark.Length; i++) mark[i] = true ; // Use the found primes by // simpleSieve() to find // primes in current range for ( int i = 0; i < prime.Count; i++) { // Find the minimum number in // [low..high] that is a multiple // of prime.get(i) (divisible by // prime.get(i)) For example, // if low is 31 and prime.get(i) // is 3, we start with 33. int loLim = (( int )Math.Floor(( double )(low / ( int )prime[i])) * ( int )prime[i]); if (loLim < low) loLim += ( int )prime[i]; /* Mark multiples of prime.get(i) in [low..high]: We are marking j - low for j, i.e. each number in range [low, high] is mapped to [0, high-low] so if range is [50, 100] marking 50 corresponds to marking 0, marking 51 corresponds to 1 and so on. In this way we need to allocate space only for range */ for ( int j = loLim; j < high; j += ( int )prime[i]) mark[j-low] = false ; } // Numbers which are not marked as false are prime for ( int i = low; i < high; i++) if (mark[i - low] == true ) Console.Write(i + " " ); // Update low and high for next segment low = low + limit; high = high + limit; } } // Driver code static void Main() { int n = 100; Console.WriteLine( "Primes smaller than " + n + ":" ); segmentedSieve(n); } } // This code is contributed by mits |
输出：
Primes smaller than 100:2 3 5 7 11 13 17 19 23 29 31 37 4143 47 53 59 61 67 71 73 79 83 89 97
请注意，分段筛选的时间复杂度（或操作数）与 简易筛 。它对大“n”有优势，因为它具有更好的引用局部性，从而允许CPU进行更好的缓存，并且需要更少的内存空间。 本文由Utkarsh Trivedi撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
