题目10：计算两百万以下所有质数的和

欧拉计划

Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

题目：

10 以下的质数的和是 2 + 3 + 5 + 7 = 17。

找出两百万以下所有质数的和。

牡丹花下死做鬼

这不就是欧拉的题目么 谢谢翻译O(∩_∩)O哈！ 当时刚学C时我做了十多题 但是怎奈英语太烂翻译出来的 ........ 高考考完后我一定来捧场

翅膀团

#include <stdio.h>
#define NUM 2000000

int main(void)
{
    int i,j,result=0;
   
    for(i=2;i<NUM;i++)
    {
    for(j=2;j<i;j++)
    {
    if(i % j ==0)
    {
    goto z;
    }   
    }
    result += i;
z:  j=2;
    }
    printf("%d\n",result);
}

如果有错误希望指出

牡丹花下死做鬼

翅膀团 发表于 2015-7-17 21:04
#include
#define NUM 2000000

printf("%d\n",result);
就看你这一句就知道肯定错

翅膀团

牡丹花下死做鬼 发表于 2015-7-19 21:59
printf("%d\n",result);
就看你这一句就知道肯定错

还请指明哪里错了，这个办法虽然笨了点，慢了点，但还是能算出结果的

牡丹花下死做鬼

翅膀团 发表于 2015-7-20 15:20
还请指明哪里错了，这个办法虽然笨了点，慢了点，但还是能算出结果的

你确定 int 装的下

翅膀团

牡丹花下死做鬼 发表于 2015-7-21 08:11
你确定 int 装的下

你的机子int的范围我不知道，但我的机子的int是4字节，即-2147483648 ~ +2147483647 。2百万还是装得下的

mysteri0n

#python 2.7.11

def isprime(num):
    for i in range(2,int(num**0.5)+1):
        if num % i == 0:
            return False
    return True

print 2 + sum(num for num in xrange(3,2000000,2) if isprime(num))

ppsuc_wuj

楼上的运行了半天出不来，效率太低了，这个秒出答案。判断质数的最快的方法。


int main()
{
    long i,j,gab=2,count,total=3,sum=10;
    long prime[1000000]={2,3,5};
    for(i=7;i<2000000;i+=gab)
    {
        count=1;
        gab=6-gab;
        for(j=0;prime[j]*prime[j]<=i;j++)
        {
            if(i%prime[j]==0)
            {
                count=0;
                break;
            }
        }
        if(count)
        {
            prime[total]=i;
            total++;
            sum+=i;
        }
    }
    printf("%ld\n",sum);
}


答案  142913828922

huomqh

list1=[2]
x=1
sum1=2
while x<=2000000:
    a=1
    x+=2
    for i in list1:
        if i**2>x:
            break
        if x%i==0:
            a=0
            break
    if a:
        sum1+=x
        list1.append(x)
print(sum1)

142913828922

purplenight

# 修改自我的另一份代码, 部分代码或差劲, 能出结果就行.

time ./sum200 
(p) 2
(p) 3
(p) 5
(p) 0
(p) 0
(next)(p) 148933
(prime p) 0
sum 142913828922.000000

real        0m0.685s
user        0m0.648s
sys        0m0.024s

#include <stdio.h>
#include <math.h>

#define LEN 2000000
int main(){
    static int prime[LEN] = {2, 3, 5};
    static int num[LEN] = {0, 0, 2, 3, 0, 5};
    int i, j;
    int p, root, found;
    double sum;

    for (i=0; i<5; i++) {
        printf("(p) %d\n", prime[i]);
    }

    for (i=6; i<LEN;) {
        i++;
        num[i] = i;
        i++;
    }

    for (i=6; i<LEN;) {
        i += 3;
        num[i] = 0;
    }

    for (i=5; i<LEN;) {
        i += 5;
        num[i] = 0;
    }

    p = 3;
    printf("(next)");
    for (i=7; i<LEN;i++) {
        if (num[i] > 0) {
            root = (int)sqrt(num[i]);
            for (j=3; j<root; j++) {
                if (prime[j] > root ) {
                    found = 1;
                    break;
                }
                if (num[i] % prime[j] == 0) {
                    found = 0;
                    break;
                }
                else {
                    found = 1;
                }
            }
            if (found == 1) {
                prime[p] = num[i];
                p++;
                if (p == LEN) {
                    break;
                }
            }
        }
    }

    printf("(p) %d\n", p);
    printf("(prime p) %d\n", prime[p]);
    for (sum=0,i=0;i<LEN;i++){
        sum += prime[i];
    }
    printf("sum %lf\n", sum);
}

purplenight

huomqh 发表于 2016-6-13 17:33
142913828922

time pypy prime.py 
142913828922

real        0m1.345s
user        0m1.228s
sys        0m0.024s
time python2 prime.py 
142913828922

real        0m20.487s
user        0m18.916s
sys        0m0.024s
time python3 prime.py 
142913828922

real        0m52.103s
user        0m48.540s
sys        0m0.044s
pypy --version
Python 2.7.10 (5.3.1+dfsg-1, Jun 18 2016, 12:54:36)
[PyPy 5.3.1 with GCC 5.4.0 20160609]
python --version
Python 2.7.11
python3 --version
Python 3.5.2

purplenight

ppsuc_wuj 发表于 2016-3-1 23:04
楼上的运行了半天出不来，效率太低了，这个秒出答案。判断质数的最快的方法。

time ./prime 
142913828922.000000

real        0m0.614s
user        0m0.592s
sys        0m0.000s

purplenight

mysteri0n 发表于 2016-1-24 13:36

$  time pypy prime.py 
142913828922

real        0m5.094s
user        0m4.712s
sys        0m0.016s
$  time python2 prime.py 
142913828922

real        0m58.416s
user        0m53.648s
sys        0m0.016s
$  time python3 prime.py 
142913828922

real        1m21.485s
user        1m19.448s
sys        0m0.024s

QingXin

import math

def find_prime(max_x):
    prime_list = [2,3,5,7]

    k = 9
    while k<max_x:
        total_yushu = 0
        square_root = math.sqrt(k)
        for each in prime_list:
            if each > square_root:
                break
            if k%each ==0:
                total_yushu = 1
                break
        if total_yushu == 0:
            prime_list.append(k)
        k+=2

    return prime_list

if __name__=='__main__':
    import timeit
    import math
    print(sum(find_prime(2000000)))

结果是142913828922

jerryxjr1220

def isPrime(n):
        if n == 2: return True
        elif n%2 == 0: return False
        elif (n-1)/6 != int((n-1)/6) or (n+1)/6 != int((n+1)/6): return False
        else:
                for i in range(3,int(n**0.5+1),2):
                        if n%i == 0: return False
                return True

cal, summ = 3, 2
while cal < 2000000:
        if isPrime(cal): summ += cal
        cal += 2
print summ

========================
142913828922
[Finished in 9.7s]

jerryxjr1220

最快的求质数的方法：
142913828922
[Finished in 1.8s]

def getPrime(n):
        primes = [True]*n
        primes[0],primes[1]=False,False
        for (i, prime) in enumerate(primes):
                if prime:
                        for j in range(i*i,n,i): primes[j] = False
        return [k for (k,trueprime) in enumerate(primes) if trueprime]

print (sum(getPrime(2000000)))

776667

def is_prime(number):
    if number in [0,1]:
        return False
    if number == 2:
        return True
    for i in range(2,int(number**0.5)+1):
        if not number%i:
            return False
    return True

def euler(x):
    return sum([y for y in range(x+1) if is_prime(y)])

if __name__ == '__main__':
    print(euler(2000000))

376103327

import math
list1 = []
for i in range(2, 2000000+1):
    for j in range(2, int(math.sqrt(i))+1):
        if i % j == 0:
            break
    else:
        print i
        list1.append(i)
print sum(list1)

tsembrace

#找出两百万以下所有质数的和
import math
import time

def isPrime(n):
    if n<2:
        return False
    elif n==2:
        return True
    else:
        m=int(math.sqrt(n))
        for i in range(2,m+1):
            if n%i==0:
                return False
        return True

def primeSum(n):
    s=0
    for i in range(1,n):
        if isPrime(i):
            s+=i
    return s

start=time.clock()

print("两百万以内的质数之和为："+str(primeSum(2000000)))

end=time.clock()

print("耗时："+str(end-start)+"秒")