论坛 › Python交流 › 我就想问问你们2000000素数之和跑了多久

liliya 发表于 2020-5-5 17:26:57

我就想问问你们2000000素数之和跑了多久

{:9_230:} 我的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):
                ifnum%i == 0:
                  return False
            else:
                return True #没有数则为素数
    return False
result=sum(i for i in range(2000000) if is_prime(i))
print(result)

wuqramy 发表于 2020-5-5 17:28:54

用生成器
否则卡死
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()

永恒的蓝色梦想 发表于 2020-5-5 17:30:04

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

你这效率直接炸了，用素数筛，不到一秒#include<iostream>
using namespace std;
bool primes;


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

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

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

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

永恒的蓝色梦想 发表于 2020-5-5 17:31:27

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

wuqramy 发表于 2020-5-5 17:31:39

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

用蟒蛇实现啊啊啊

liliya 发表于 2020-5-5 17:32:02

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

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

liliya 发表于 2020-5-5 17:32:33

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

你这是C语言吗///？？？好像不是Python{:9_241:}

wuqramy 发表于 2020-5-5 17:32:43

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

4秒左右
不要急得关程序

永恒的蓝色梦想 发表于 2020-5-5 17:32:53

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

C++

永恒的蓝色梦想 发表于 2020-5-5 17:33:41

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

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

liliya 发表于 2020-5-5 17:38:55

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

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

永恒的蓝色梦想 发表于 2020-5-5 17:44:33

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

primes=*1000000
primes=False
primes=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=False

print(sum)718ms 出结果

liliya 发表于 2020-5-5 17:52:43

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

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

永恒的蓝色梦想 发表于 2020-5-5 17:54:18

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

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

wuqramy 发表于 2020-5-5 17:54:27

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

真quickly

liliya 发表于 2020-5-5 17:55:59

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

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

Pythonnewers 发表于 2020-5-6 10:56:23

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

C

查看完整版本: 我就想问问你们2000000素数之和跑了多久