[已解决]我就想问问你们2000000素数之和跑了多久

liliya

我的2000000素数之和跑了好久还没获得答案，长到我觉得是不是我程序有问题了。

def is_prime(num):
    if num > 1:
        if num ==2:
            return True #2是素数
        elif num == 3:
            return True #3是素数
        else:
            for i in range(2,num):
                if  num%i == 0:
                    return False
            else:
                return True #没有数则为素数
    return False
result=sum(i for i in range(2000000) if is_prime(i))
print(result) 

最佳答案

月排行榜 / 总排行榜

永恒的蓝色梦想

2020-5-5 17:44:33

liliya 发表于 2020-5-5 17:38
我知道原因了，我判断素数的时候太慢了，我改成一半儿的来判断就好使了。果然。

primes=[False,True]*1000000
primes[1]=False
primes[2]=True
sum=0


for num,i in enumerate(primes):
    if i:
        sum+=num
        temp=num<<1
        for num in range(num+temp,2000000,temp):
            primes[num]=False

print(sum)

718ms 出结果

跳转到最佳答案楼层

wuqramy

用生成器
否则卡死

import math
def is_prime(number):
    if number > 1:
        if number == 2:
            return True
        if number % 2 == 0:
            return False
        for each in range(3,int(math.sqrt(number) + 1),2):
            if number % each == 0:
                return False
        return True
    return False
def get_primes(number):
    while True:
        if is_prime(number):
            yield number
        number += 1
def solve():
    total = 2
    for next_prime in get_primes(3):
        if next_prime < 2000000:
            total += next_prime
        else:
            print(total)
            return
if __name__ == '__main__':
    solve()

永恒的蓝色梦想

wuqramy 发表于 2020-5-5 17:28
用生成器
否则卡死

你这效率直接炸了，用素数筛，不到一秒

#include<iostream>
using namespace std;
bool primes[2000000U];


int main() {
    unsigned long long sum = 2;
    unsigned int i, j, k;

    for (i = 3; i < 2000000U; i += 2) {
        if (!primes[i]) {
            sum += i;
            k = i << 1;

            for (j = i + k; j < 2000000U; j += k) {
                primes[j] = true;
            }
        }
    }

    cout << sum << endl;
    return 0;
}

永恒的蓝色梦想

Project Euler里的大部分题目都不能用暴力解的

wuqramy

永恒的蓝色梦想 发表于 2020-5-5 17:30
你这效率直接炸了，用素数筛，不到一秒

用蟒蛇实现啊啊啊

liliya

wuqramy 发表于 2020-5-5 17:28
用生成器
否则卡死

我用的是生成器呀，我用你这个程序也运行好久没结果。我原来偷了个懒直接用的生成器推导式，你这个程序跑了多久

liliya

永恒的蓝色梦想 发表于 2020-5-5 17:30
你这效率直接炸了，用素数筛，不到一秒

你这是C语言吗///？？？好像不是Python

wuqramy

liliya 发表于 2020-5-5 17:32
我用的是生成器呀，我用你这个程序也运行好久没结果。我原来偷了个懒直接用的生成器推导式，你这个程序跑 ...

4秒左右
不要急得关程序

永恒的蓝色梦想

liliya 发表于 2020-5-5 17:32
你这是C语言吗///？？？好像不是Python

C++

永恒的蓝色梦想

liliya 发表于 2020-5-5 17:32
你这是C语言吗///？？？好像不是Python

稍微一等，给你来个高效Python

liliya

永恒的蓝色梦想 发表于 2020-5-5 17:33
稍微一等，给你来个高效Python

我知道原因了，我判断素数的时候太慢了，我改成一半儿的来判断就好使了。果然。

永恒的蓝色梦想

liliya 发表于 2020-5-5 17:38
我知道原因了，我判断素数的时候太慢了，我改成一半儿的来判断就好使了。果然。

primes=[False,True]*1000000
primes[1]=False
primes[2]=True
sum=0


for num,i in enumerate(primes):
    if i:
        sum+=num
        temp=num<<1
        for num in range(num+temp,2000000,temp):
            primes[num]=False

print(sum)

718ms 出结果

liliya

永恒的蓝色梦想 发表于 2020-5-5 17:44
718ms 出结果

讲道理你这是怎么判断素数的

永恒的蓝色梦想

liliya 发表于 2020-5-5 17:52
讲道理你这是怎么判断素数的

埃氏筛法，任何一个质数的倍数都不是质数

wuqramy

永恒的蓝色梦想 发表于 2020-5-5 17:44
718ms 出结果

真quickly

liliya

永恒的蓝色梦想 发表于 2020-5-5 17:54
埃氏筛法，任何一个质数的倍数都不是质数

你真强啊大兄弟！我以前完全都没听过这方法，牛逼牛逼。

Pythonnewers

liliya 发表于 2020-5-5 17:32
你这是C语言吗///？？？好像不是Python

C