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

liliya

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

1. def is_prime(num):
   
2.     if num > 1:
   
3.         if num ==2:
   
4.             return True #2是素数
   
5.         elif num == 3:
   
6.             return True #3是素数
   
7.         else:
   
8.             for i in range(2,num):
   
9.                 if  num%i == 0:
   
10.                     return False
    
11.             else:
    
12.                 return True #没有数则为素数
    
13.     return False
    
14. result=sum(i for i in range(2000000) if is_prime(i))
    
15. print(result)

复制代码

最佳答案

月排行榜 / 总排行榜

永恒的蓝色梦想

2020-5-5 17:44:33

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

1. primes=[False,True]*1000000
   
2. primes[1]=False
   
3. primes[2]=True
   
4. sum=0
   
5. 
   
6. 
   
7. for num,i in enumerate(primes):
   
8.     if i:
   
9.         sum+=num
   
10.         temp=num<<1
    
11.         for num in range(num+temp,2000000,temp):
    
12.             primes[num]=False
    
13. 
    
14. print(sum)

复制代码

718ms 出结果

跳转到最佳答案楼层

wuqramy

用生成器
否则卡死

1. import math
   
2. def is_prime(number):
   
3.     if number > 1:
   
4.         if number == 2:
   
5.             return True
   
6.         if number % 2 == 0:
   
7.             return False
   
8.         for each in range(3,int(math.sqrt(number) + 1),2):
   
9.             if number % each == 0:
   
10.                 return False
    
11.         return True
    
12.     return False
    
13. def get_primes(number):
    
14.     while True:
    
15.         if is_prime(number):
    
16.             yield number
    
17.         number += 1
    
18. def solve():
    
19.     total = 2
    
20.     for next_prime in get_primes(3):
    
21.         if next_prime < 2000000:
    
22.             total += next_prime
    
23.         else:
    
24.             print(total)
    
25.             return
    
26. if __name__ == '__main__':
    
27.     solve()
    

复制代码

永恒的蓝色梦想

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

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

1. #include<iostream>
   
2. using namespace std;
   
3. bool primes[2000000U];
   
4. 
   
5. 
   
6. int main() {
   
7.     unsigned long long sum = 2;
   
8.     unsigned int i, j, k;
   
9. 
   
10.     for (i = 3; i < 2000000U; i += 2) {
    
11.         if (!primes[i]) {
    
12.             sum += i;
    
13.             k = i << 1;
    
14. 
    
15.             for (j = i + k; j < 2000000U; j += k) {
    
16.                 primes[j] = true;
    
17.             }
    
18.         }
    
19.     }
    
20. 
    
21.     cout << sum << endl;
    
22.     return 0;
    
23. }

复制代码

永恒的蓝色梦想

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
我知道原因了，我判断素数的时候太慢了，我改成一半儿的来判断就好使了。果然。

1. primes=[False,True]*1000000
   
2. primes[1]=False
   
3. primes[2]=True
   
4. sum=0
   
5. 
   
6. 
   
7. for num,i in enumerate(primes):
   
8.     if i:
   
9.         sum+=num
   
10.         temp=num<<1
    
11.         for num in range(num+temp,2000000,temp):
    
12.             primes[num]=False
    
13. 
    
14. 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