用python求出2000000内所有素数的和?不知怎么写?

发布网友 发布时间：2022-04-18 09:41

我来回答

共5个回答

懂视网 时间：2022-04-18 14:03

回复内容：

#include 
#include 
#include 
#include 

#define PRIME_LIM 10000000
#define N 100000000

int primes[PRIME_LIM] = {0};
int flags[N/96 + 1] = {0};

int get_prime()
{
 int nu = 5, to = 0;
 primes[0] = 2;
 primes[1] = 2, primes[2] = 3;
 for(int i = 0; nu <= N; i++) {
 if(!(flags[i>>5]&(1<<(i&31)))) primes[++primes[0]] = nu;
 for(int j = 3; j <= primes[0] && primes[j] * nu <= N; j++) {
  to = (nu * primes[j] - 5) >> 1;
  to -= to/3;
  flags[to>>5] |= 1<<(to&31);
  if(!(nu % primes[j])) break;
 }
 nu += 2 + ((i&1) << 1);
 }
 return primes[0];
}

int main()
{
 clock_t t = clock();
 printf("%d
", get_prime());
 printf("Time:%f
", 1.0 * (clock() - t) / CLOCKS_PER_SEC);
 for(int i = 1; primes[i] < 100; i++) {
 printf("%d
", primes[i]);
 }
 return 0;
}

class Prime{	
	public static int calculateNumber(int Nmax){
		boolean[] isPrime=new boolean[Nmax+1];		
		for(int i=3;i<=Nmax;i+=2)
			isPrime[i]=true;
		isPrime[2]=true;
		for(int i=3;i<=Math.sqrt(Nmax);i+=2){
			if(isPrime[i]==true){
				for(int j=i*i;j<=Nmax;j+=2*i)
					isPrime[j]=false;
			}
		}
		int primeNum=0;
		for(int i=1;i<=Nmax;i++){
			if(isPrime[i]==true)
				primeNum++;
		}
		return primeNum;
	}				
	public static void main(String[] args){
		final int Nmax=2000000;
		double startTime=System.currentTimeMillis();
		int primeNum=Prime.calculateNumber(Nmax);
		double timeSpent=(System.currentTimeMillis()-startTime)/1000;
		System.out.println("The prime numbers from 1 to "+Nmax+" is "+primeNum);
		System.out.println("Time spent : "+timeSpent+" s");
	}
}

#include 
#include 
#include 
#include 
const int N = 2000000;
bool b[N+1];
int c[N+1];
void Era_select(){ // Eratosthenes
	memset(b, 0, N+1);
	int q = (int)sqrt(N);
	int i, j, cnt = 0;
	for ( i=2; i<=q; ++i ){
		if ( ! b[i] ){
			for ( j=i<<1; j<=N; j+=i ){
				b[j] = true;
			}
		}
	}
	for ( i=2; i<=N; ++i ){
		if ( ! b[i] ){
			++cnt;
		}
	}
	//printf("%d
", cnt);
}
void Euler_select(){
	memset(b, 0, N+1);
	int i, j, cnt = 0, t;
	for ( i=2; i<=N; ++i ){
		if ( ! b[i] ){
			c[cnt++] = i;
		}
		for ( j=0; j N ){
				break;
			}
			b[t] = true;
			if ( i%c[j] == 0 ){
				break;
			}
		}
	}
	//printf("%d
", cnt);
}
int main(){
	int i, num=100;
	clock_t start;
	start = clock();
	for ( i=0; i

def rwh_primes2(n = 10**6):
 # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
 """ Input n>=6, Returns a list of primes, 2 <= p < n """
 correction = (n%6>1)
 n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
 sieve = [True] * (n/3)
 sieve[0] = False
 for i in xrange(int(n**0.5)/3+1):
 if sieve[i]:
 k=3*i+1|1
 sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
 sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
 return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]