题目7：找出第10001个质数

xuan1788

1. """
   
2. To find the nth prime
   
3. """
   
4. import math
   
5. from math import sqrt, floor
   
6. 
   
7. def is_prime(a):
   
8.     if a == 2:
   
9.         return True
   
10.     for i in range(2, floor(sqrt(a))+1):
    
11.         if a % i == 0:
    
12.             return False
    
13.     return True
    
14. 
    
15. def getNthPrime(n):
    
16.     x = 2
    
17.     if n == 1:
    
18.         return 2
    
19.     if n == 2:
    
20.         return 3
    
21.     p = 3
    
22.     while x < n:
    
23.         p += 2
    
24.         if is_prime(p):
    
25.             x += 1
    
26.     return p
    

复制代码

yhhpf

1. flag = 1
   
2. a = 1
   
3. b = 1
   
4. while flag:
   
5.     a += 2
   
6.     c = 3
   
7.     while c <= a ** 0.5 :
   
8.         if a % c == 0:
   
9.             break
   
10.         c += 2
    
11.     if c > a**0.5:
    
12.         b += 1
    
13.     if b == 10001:
    
14.         flag = 0
    
15. print(a)

复制代码

4444567

1. from time import time
   
2. from math import sqrt
   
3. 
   
4. def prime(x):
   
5.     if x <= 2:
   
6.         print('error')
   
7.     else:
   
8.         if x%2 == 0:
   
9.             return False
   
10.         for i in range(3,int(sqrt(x))+1,2):
    
11.             if  x%i == 0:
    
12.                 return False
    
13.         return x
    
14.    
    
15. t1 = time()      
    
16. m = [2,3,5,7,11,13]
    
17. i = 14
    
18. while True:
    
19.     if prime(i):
    
20.         m.append(i)
    
21.     if len(m) == 10001:
    
22.         print(m[-1])
    
23.         break
    
24.     i += 1
    
25. 
    
26. t2 = time()
    
27. t=t2-t1
    
28. print('耗时为：%s' % t)   
    

复制代码

有马_冬巳

1. '''前六个质数是 2, 3, 5, 7, 11 和 13，其中第 6 个是 13。
   
2. 第 10001 个质数是多少？'''
   
3. 
   
4. def numprime(position):
   
5.     a = 8
   
6.     prime_sequence = [2,3,5,7]
   
7.     while len(prime_sequence) < position:
   
8.         for prime in range(2,int(a/2)):
   
9.             check = 0
   
10.             if a%prime == 0:
    
11.                 check += 1
    
12.                 break
    
13.         if check == 0:
    
14.             prime_sequence.append(a)
    
15.         a += 1
    
16.     print("第%d个质数是: %d" %(position,prime_sequence[position-1]))
    
17. 
    
18. start_numprime = time.time()
    
19. numprime(10001)
    
20. time_numprime = time.time() - start_numprime
    
21. print("%f秒" %time_numprime)

复制代码

第10001个质数是: 104743
17.688404秒

gonorth

import math as m


def is_prime(n):
    if n > 1:
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        for each in range(3, int(m.sqrt(n )) + 1, 2):
            if n % each == 0:
                return False
        return True
    return False


def get_prime(n):
    while 1:
        if is_prime(n):
            yield n
        n = n + 1


def solve():
    count = 0
    for i in get_prime(1):
        count = count + 1
        if count + 1> 10001:
            break
    return i


print(solve())

a1351468657

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. main()
   
5. {
   
6.         int count = 0, num, i, j = 2, flag = 1;
   
7.         while (1)
   
8.         {
   
9.                 for (i = 2; i < sqrt(j + 1); i++)
   
10.                 {
    
11.                         if (j % i == 0)
    
12.                         {
    
13.                                 flag = 0;
    
14.                         }
    
15.                 }
    
16.                 if (flag == 1)
    
17.                 {
    
18.                         count++;
    
19.                 }
    
20.                 if (count == 10001)
    
21.                 {
    
22.                         printf("\n第100001个质数是：%d\n", j);
    
23.                         break;
    
24.                 }
    
25.                 j++;
    
26.                 flag = 1;
    
27.         }
    
28. }

复制代码

老师帮我看看效率怎样，基本秒出答案， 104743

永恒的蓝色梦想

a1351468657 发表于 2021-3-6 15:38
老师帮我看看效率怎样，基本秒出答案， 104743

如果没开优化, 第9行的判断条件会不断调用sqrt, 严重浪费性能。
质数筛法会比普通的判断质数快。

Kuri5u

1. flag=True
   
2. result=2
   
3. time=2
   
4. i=5
   
5. while time<=10001:
   
6.     for each in range (2,i//2+1):
   
7.         if i % each == 0:
   
8.             flag=0
   
9.             i+=1
   
10.             break
    
11.     if flag:
    
12.         result=i
    
13.         time+=1
    
14.         i+=1
    
15.     else:
    
16.         flag=1
    
17. print(result)
    

复制代码

104743

卢本伟牛逼

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int count = 0;
   
5. 
   
6. int is_prime(int value)
   
7. {
   
8.         int i=2;
   
9.         for(i;i<sqrt(value);i++)//改进1
   
10.         {
    
11.                 count += 1;
    
12.                 if (i>3) i++; //改进2
    
13.                 if (value % i == 0) return 0;
    
14.         }
    
15.         return 1;
    
16. }
    
17. 
    
18. int main(void)
    
19. {
    
20.         int flag = 1;
    
21.         int i = 3;
    
22.         while(1)
    
23.         {
    
24.                 if (is_prime(i)) flag += 1;
    
25.                 if (flag >= 10001) break;
    
26.                 i += 2;//改进3
    
27.         }
    
28.        
    
29.         printf("result = %d\n", i);
    
30.         printf("count = %d\n", count);//count = 1491484
    
31.         return 0;
    
32. }

复制代码

鱼塘里的鱼儿

#include <iostream>
using namespace std;
int main()
{
        int sum=0,i=2;
        for(;;i++)
        {
         for(int i1=2;i1<i;i1++)
         {
                 if(i%i1==0)
                         break;
                 if(i1==(i-1))
                         sum++;
         }
         if(sum==10001)
         {
                 cout<<i<<endl;
                 break;
         }
        }
        return 0;
}

\\C++写的答案：104759

ft215378

#生成输入值范围内的素数（质数）返回列表
from math import *
#判断是否是素数
def is_prime(number):
    if number > 1:
        if number == 2:
            return True
        if number % 2 == 0:
            return False
        for a in range(3,int(sqrt(number) + 1),2):
            if number % a == 0:
                return False
        return True
    return False
#生成素数列表，得到num以内的素数（返回列表primelist）
primelist = []
num = 110000

while 1:
    for i in range(2, num + 1):
        if is_prime(i):
            primelist.append(i)
            if len(primelist) == 10000:
                break

   
    break



   

番杰

1. #include<stdio.h>
   
2. 
   
3. int mian(void)
   
4. {
   
5.         int result,flag = 0 ,num = 6;
   
6.        
   
7.         for(int i = 13;;i++)
   
8.         {
   
9.                  for(int j = 2;j<(i/2);j++)
   
10.                  (
    
11.                         if(i / j == 0)
    
12.                         {
    
13.                                 flag = 1;
    
14.                                 break;
    
15.                         }
    
16.                 )
    
17.                
    
18.                 if(flag == 1)
    
19.                         flag = 0;
    
20.                 else
    
21.                 {
    
22.                         num++;
    
23.                         if(num == 10001)
    
24.                         {
    
25.                                 result = i;
    
26.                                 break;
    
27.                         }
    
28.                 }
    
29.         }
    
30.        
    
31.         printf("%d",result;
    
32.        
    
33.         return 0；
    
34. }

复制代码

guosl

这个题目的大多数解都是通过整除性质来判断一个整数是否是一个素数，但这会耗费大量的时间，在此我用了筛法，时间大大地缩短了。

1. /*
   
2. 答案：104743
   
3. 耗时：0.0006446秒
   
4. */
   
5. #include <iostream>
   
6. #include <cstring>
   
7. using namespace std;
   
8. 
   
9. const int N = 200004;
   
10. 
    
11. char cp[N];
    
12. 
    
13. int main(void)
    
14. {
    
15.   memset(cp + 2, 1, sizeof(char) * (N - 2));
    
16.   for (int i = 2; i <= 447; ++i)
    
17.   {
    
18.     if (cp[i] == 0)
    
19.       continue;
    
20.     for (int j = i * i; j <= N - 4; j += i)
    
21.       cp[j] = 0;
    
22.   }
    
23.   int nCount = 1;
    
24.   for (int i = 3; i <= N - 4; i += 2)
    
25.   {
    
26.     if (cp[i] == 1)
    
27.     {
    
28.       ++nCount;
    
29.       if (nCount == 10001)
    
30.       {
    
31.         cout << i << endl;
    
32.         break;
    
33.       }
    
34.     }
    
35.   }
    
36.   return 0;
    
37. }

复制代码

mathtimes

2.1s

1. prime = [2,3]
   
2. i = 4
   
3. while len(prime)<10001:
   
4.     s = True
   
5.     for j in prime:
   
6.         if i%j == 0:
   
7.             s = False
   
8.             break
   
9.     if s:
   
10.         prime.append(i)
    
11.     i = i + 1
    
12. print(prime[-1])

复制代码

0.5s

1. #include <stdio.h>
   
2. #include <vector>
   
3. using std::vector;
   
4. int main()
   
5. {
   
6.     vector<long long> prime;
   
7.     vector<long long>::iterator it;
   
8.     long long i;   
   
9.     prime.push_back(2);
   
10.     for(i=2;i<__LONG_LONG_MAX__&&prime.size()<10001;i++)
    
11.     {
    
12.         for(it=prime.begin();it!=prime.end();it++)
    
13.         {
    
14.             if(i%*it==0)
    
15.                 goto loop;
    
16.         }
    
17.         prime.push_back(i);  
    
18.         loop:;
    
19.     }         
    
20.     printf("%lld",*(prime.end()-1));
    
21. }

复制代码

Kazimierz

结果104759

1. #include <stdio.h>
   
2. #define NUM 10001
   
3. 
   
4. int main()
   
5. {
   
6.         int i,n=0,s=0,x=3;
   
7.        
   
8.         while(s<NUM)
   
9.         {
   
10.                 for(i=2;i<x;i++)
    
11.                 {
    
12.                         if(x%i==0){
    
13.                                 n++;
    
14.                                 x++;
    
15.                                 break;
    
16.                         }
    
17.                 }
    
18.                
    
19.                 if(n==0){
    
20.                         s++;
    
21.                         x++;
    
22.                         continue;
    
23.                 }
    
24.                
    
25.                 n=0;
    
26.         }
    
27.         printf("%d",x-1);
    
28.         return 0;
    
29.        
    
30. }

复制代码

jerryxjr1220

冗余设计用了长度1000000的列表，如果只考虑20万左右的列表，可以再缩小5倍的时间。

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5.         "time"
   
6. )
   
7. 
   
8. //题目6：
   
9. //
   
10. //前六个质数是 2, 3, 5, 7, 11 和 13，其中第 6 个是 13。
    
11. //
    
12. //第 10001 个质数是多少？
    
13. func main() {
    
14.         t := time.Now()
    
15.         var nums [1000000]int
    
16.         nums[0] = 1
    
17.         nums[1] = 1
    
18. 
    
19.         for i := 2; i < 1000; i++ {
    
20.                 var j int
    
21.                 for j = i * i; j < 1000000; j += i {
    
22.                         nums[j] = 1
    
23.                 }
    
24.         }
    
25.         var c int = 0
    
26.         var count int = 0
    
27.         for c = 2; c < 1000000; c++ {
    
28.                 if nums[c] == 0 {
    
29.                         count++
    
30.                 }
    
31.                 if count == 10001 {
    
32.                         fmt.Println(c)
    
33.                         break
    
34.                 }
    
35.         }
    
36.         tt := time.Now()
    
37.         fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
    
38. }
    

复制代码

输出：

1. C:\Users\Anaconda\GolandProjects\EulerProject\output\go_build_Euler06_go.exe
   
2. 104743
   
3. 耗时： 19 ms
   
4. 
   
5. 进程 已完成，退出代码为 0

复制代码

Go语言还真是快

Asss-whom

这种暴算的任务Rust + Rayon轻松解决：
（抄的RustCC的代码）

1. use rayon::prelude::*;
   
2. use std::time::Instant;
   
3. 
   
4. const N: i32 = 200000;
   
5. 
   
6. fn main() {
   
7.     let now = Instant::now();
   
8.     let mut primes = Vec::new();
   
9.     let mut cur = 10;
   
10.     // bootstrap
    
11.     for i in 2..cur {
    
12.         if primes.iter().all(|p| i % p != 0) {
    
13.             primes.push(i);
    
14.         }
    
15.     }
    
16.     while cur < N {
    
17.         let next = std::cmp::min(cur * cur, N);
    
18.         let mut addition: Vec<_> = (cur..next)
    
19.             .into_par_iter()
    
20.             .filter(|x| {
    
21.                 for p in primes.iter() {
    
22.                     if x % p == 0 {
    
23.                         return false;
    
24.                     }
    
25.                     if x / p < *p {
    
26.                         break;
    
27.                     }
    
28.                 }
    
29.                 true
    
30.             })
    
31.             .collect();
    
32.         primes.append(&mut addition);
    
33.         cur = next;
    
34.     }
    
35.     println!("{}", primes[10001]);
    
36.     println!("耗时{}毫秒。", now.elapsed().as_millis())
    
37. }
    

复制代码

---
104759
耗时3毫秒。

歌者文明清理员

zxc123qwe 发表于 2016-4-26 13:04
这代码怎么弄上去的，还能粘贴复制显示行数。教教我吧

https://fishc.com.cn/thread-52272-1-1.html

Eca

1. #include <stdio.h>
   
2. 
   
3. int main() {
   
4.         long long int i = 1, num = 0, j = 0;
   
5.         while (num < 10001) {
   
6.                 for ( j = 2; j < i; j++) {
   
7.                         if (i % j == 0)
   
8.                                 break;
   
9.                 }
   
10.                 if (j == i)
    
11.                         num++;
    
12.                 i++;
    
13.         }
    
14. 
    
15.         printf("%d", i - 1);
    
16. }

复制代码

感觉写的一般，应该有更好的方法