给定一个数字N。如果该数字不是素数，则通过从2开始依次添加素数使其成为素数，从而打印最近的素数。 例如：
null
输入： N=8 输出： 13 8不是素数，所以把第一个素数加起来就得到10 10不是素数，因此加上第二个素数，即3得到13，这是素数。 输入： N=45 输出： 47
方法 使用 埃拉托斯坦筛 ，将主索引标记为1英寸 iPrime[] 列出并存储列表中的所有素数 素数 .继续把素数顺序加到N上，直到N变成素数。 以下是上述方法的实施情况：
C++
// C++ program to print the // nearest prime number by // sequentially adding the // prime numbers #include<bits/stdc++.h> using namespace std; // Function to store prime // numbers using prime sieve void prime_sieve( int MAX, vector< int > &isprime, vector< int > &prime) { // iterate for all // the numbers int i = 2; while (i * i <= MAX) { // If prime[p] is not changed, // then it is a prime if (isprime[i] == 1) { // append the prime // to the list prime.push_back(i); // Update all multiples of p for ( int j = i * 2; j < MAX; j += i) { isprime[j] = 0; } } i += 1; } } // Function to print // the nearest prime int printNearest( int N) { int MAX = 1e6; // store all the // index with 1 vector< int > isprime(MAX, 1); // 0 and 1 are not prime isprime[0] = isprime[1] = 0; // list to store // prime numbers vector< int > prime; // variable to // add primes int i = 0; // call the sieve function prime_sieve(MAX, isprime, prime); // Keep on adding prime // numbers till the nearest // prime number is achieved while (!isprime[N]) { N += prime[i]; i += 1; } // return the // nearest prime return N ; } // Driver Code int main() { int N = 8; printf ( "%d" , printNearest(N)); return 0; } // This code is contributed // by Harshit Saini |
JAVA
// Java program to print the // nearest prime number by // sequentially adding the // prime numbers import java.util.*; class GFG { // Function to store prime // numbers using prime sieve static void prime_sieve( int MAX, int []isprime, Vector<Integer> prime) { // iterate for all // the numbers int i = 2 ; while (i * i <= MAX) { // If prime[p] is not changed, // then it is a prime if (isprime[i] == 1 ) { // append the prime // to the list prime.add(i); // Update all multiples of p for ( int j = i * 2 ; j < MAX; j += i) { isprime[j] = 0 ; } } i += 1 ; } } // Function to print // the nearest prime static int printNearest( int N) { int MAX = ( int ) 1e6; // store all the // index with 1 except 0,1 index int [] isprime = new int [MAX]; for ( int i = 2 ; i < MAX; i++) isprime[i] = 1 ; // list to store // prime numbers Vector<Integer> prime = new Vector<Integer>(); // variable to add primes int i = 0 ; // call the sieve function prime_sieve(MAX, isprime, prime); // Keep on adding prime // numbers till the nearest // prime number is achieved while (isprime[N] == 0 ) { N += prime.get(i); i += 1 ; } // return the // nearest prime return N ; } // Driver Code public static void main(String[] args) { int N = 8 ; System.out.printf( "%d" , printNearest(N)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to print the nearest prime # number by sequentially adding the prime numbers # Function to store prime numbers using prime sieve def prime_sieve( MAX , isprime, prime): # iterate for all the numbers i = 2 while (i * i < = MAX ): # If prime[p] is not changed, # then it is a prime if (isprime[i] = = 1 ): # append the prime to the list prime.append(i) # Update all multiples of p for j in range (i * 2 , MAX , i): isprime[j] = 0 i + = 1 # Function to print the nearest prime def printNearest(N): MAX = 10 * * 6 # store all the index with 1 isprime = [ 1 ] * MAX # 0 and 1 are not prime isprime[ 0 ] = isprime[ 1 ] = 0 # list to store prime numbers prime = [] # variable to add primes i = 0 # call the sieve function prime_sieve( MAX , isprime, prime) # Keep on adding prime numbers # till the nearest prime number # is achieved while not isprime[N]: N + = prime[i] i + = 1 # return the nearest prime return N # Driver Code N = 8 print (printNearest(N)) |
C#
// C# program to print the // nearest prime number by // sequentially adding the // prime numbers using System; using System.Collections.Generic; class GFG { // Function to store prime // numbers using prime sieve static void prime_sieve( int MAX, int []isprime, List< int > prime) { // iterate for all the numbers int i = 2; while (i * i <= MAX) { // If prime[p] is not changed, // then it is a prime if (isprime[i] == 1) { // append the prime to the list prime.Add(i); // Update all multiples of p for ( int j = i * 2; j < MAX; j += i) { isprime[j] = 0; } } i += 1; } } // Function to print // the nearest prime static int printNearest( int N) { int MAX = ( int ) 1e6; int i = 0; // store all the // index with 1 except 0,1 index int [] isprime = new int [MAX]; for (i = 2; i < MAX; i++) isprime[i] = 1; // list to store // prime numbers List< int > prime = new List< int >(); // variable to add primes i = 0; // call the sieve function prime_sieve(MAX, isprime, prime); // Keep on adding prime // numbers till the nearest // prime number is achieved while (isprime[N] == 0) { N += prime[i]; i += 1; } // return the // nearest prime return N; } // Driver Code public static void Main(String[] args) { int N = 8; Console.Write( "{0}" , printNearest(N)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to print the // nearest prime number by // sequentially adding the // prime numbers // Function to store prime // numbers using prime sieve function prime_sieve(MAX, isprime, prime) { // iterate for all // the numbers var i = 2; while (i * i <= MAX) { // If prime[p] is not changed, // then it is a prime if (isprime[i] == 1) { // append the prime // to the list prime.push(i); // Update all multiples of p for ( var j = i * 2; j < MAX; j += i) { isprime[j] = 0; } } i += 1; } } // Function to print // the nearest prime function printNearest(N) { var MAX = 1e6; // store all the // index with 1 var isprime = Array(MAX).fill(1); // 0 and 1 are not prime isprime[0] = isprime[1] = 0; // list to store // prime numbers var prime = []; // variable to // add primes var i = 0; // call the sieve function prime_sieve(MAX, isprime, prime); // Keep on adding prime // numbers till the nearest // prime number is achieved while (!isprime[N]) { N += prime[i]; i += 1; } // return the // nearest prime return N ; } // Driver Code var N = 8; document.write( printNearest(N)); // This code is contributed by rrrtnx. </script> |
输出：
13
时间复杂性： O（N*log（logN）） 辅助空间： O（N）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
