题目7：找出第10001个质数

Plusenxue

1. n = 1
   
2. temp = [2]
   
3. value = 3
   
4. while n <= 10000:
   
5.     for i in temp:
   
6.         if value%i == 0:
   
7.             break
   
8.         if i == temp[-1]:
   
9.             temp.append(value)
   
10.             n += 1
    
11. 
    
12.     value += 1
    
13. 
    
14. print(temp[10000])
    

复制代码

impossible

#include <stdio.h> #include <math.h>  int isPrime(int num);  int main() {         int i,num=3;                  for(i=1;i!=10001;num+=2)         {                 if(isPrime(num))i++;         }         printf("%d",num-2);                  return 0; } int isPrime(int sum) {         int i,choose=1;                  for(i=3;i<=sqrt(sum);i+=2)         {                 if(sum%i==0)                 {                       choose=0;                       break;                 }                 }                  return choose; }

776667

1. def euler(x):
   
2.     count = 0
   
3.     number = 2
   
4.     while count < x:
   
5.         if number == 2:
   
6.             number += 1
   
7.             count += 1
   
8.             continue
   
9.         for i in range(2,number):
   
10.             if not number%i:
    
11.                 break
    
12.         else:
    
13.             count += 1
    
14.         number += 2
    
15.     return number - 2
    
16. 
    
17. if __name__ == '__main__':
    
18.     print(euler(10001))

复制代码

镜中人31

1. i = 5
   
2. j = 2
   
3. list1 = [2,3]
   
4. while True:
   
5.     for k in list1[1:]:
   
6.         if(i%k == 0):
   
7.             break
   
8.         if k == list1[j-1]:
   
9.             list1.append(i)
   
10.             j += 1
    
11.     if j == 10001:
    
12.         break
    
13.     i += 2
    
14. print(i)

复制代码

我的20来秒时间，答案104743

tsembrace

1. import time
   
2. import math
   
3. 
   
4. start=time.clock()
   
5. def isPrime(n):
   
6.     if n<2:
   
7.         return False
   
8.     elif n==2:
   
9.         return True
   
10.     else:
    
11.         m=int(math.sqrt(n))
    
12.         for i in range(2,m+1):
    
13.             if n%i==0:
    
14.                 return False
    
15.         return True
    
16. 
    
17. count=0
    
18. i=2
    
19. while count<10001:
    
20.     if isPrime(i):
    
21.         count+=1
    
22.         i+=1
    
23.         continue
    
24.     else:
    
25.         i+=1
    
26. 
    
27. print(i-1)
    
28. end=time.clock()
    
29. print("耗时"+str(end-start)+"s")
    
30.         
    
31. 
    
32. 
    

复制代码

toBeNot

1. public class The10001Prime {
   
2.         public static boolean isPrime(int n){
   
3.                 boolean flag = true;
   
4.                 for(int i = 2;i < n;i++){
   
5.                         if(n % i == 0){
   
6.                                 flag = false;
   
7.                                 break;
   
8.                         }
   
9.                 }
   
10.                 return flag;
    
11.         }
    
12.         public static void main(String[] args){
    
13.                 int number = 1;
    
14.                 int j = 0;
    
15.                 for(j = 3;number < 10001;j = j +2){
    
16.                         if(isPrime(j)){
    
17.                                 number += 1;
    
18.                         }
    
19.                 }
    
20.                 System.out.println("第10001个质数是：" + (j - 2));       
    
21.         }
    
22. }

复制代码

梦想绘制者

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

看这个帖子
http://bbs.fishc.com/forum.php?m ... amp;page=1#pid11009

梦想绘制者

1. # Python 3.5实现求第10001个质数
   
2. def isPrime(n):
   
3.     if n <= 1:
   
4.         return False
   
5.     else:
   
6.         half = int(n ** 0.5) # n // 2
   
7.         for i in range(2,half + 1):
   
8.             if n % i == 0:
   
9.                 return False
   
10.         return True
    
11. 
    
12. def nthPrime(nth):
    
13.     primeCount = 0
    
14.     num = 1
    
15.     while 1:
    
16.         num += 1
    
17.         if isPrime(num):
    
18.             primeCount += 1
    
19.         else:
    
20.             continue
    
21.         if primeCount == nth:
    
22.             return num
    
23. 
    
24. nth = 10001
    
25. print('第%d个质数为%d'%(nth, nthPrime(nth)))
    

复制代码

速度还蛮快的, 1s多就出结果。
>>>
第10001个质数为104743

lyciam

1. t = time.clock()
   
2. 
   
3. def isprime(n):
   
4.     if (n%2==0 and n!=2) or n==1: return False
   
5.     for x in range(3,int(math.sqrt(n))+1,2):
   
6.         if n%x==0 or n%5==0: return False
   
7.     else: return True
   
8. 
   
9. def euler07(num=10001):
   
10.     """第10001个质数是多少？"""
    
11.     count = 0
    
12.     n = 0
    
13.     while count<num:
    
14.         n += 1
    
15.         if isprime(n): count+=1
    
16.     return {count:n}
    
17. 
    
18. print(euler07(10001),'time:',time.clock()-t)

复制代码

{10001: 104743} time: 0.45091703770432073

芒果加黄桃

1. # encoding:utf-8
   
2. from math import sqrt
   
3. from time import time
   
4.       
   
5. def findNPrimes(number):
   
6.     if number == 1:
   
7.         return [2]
   
8.     elif number == 2:
   
9.         return [2, 3]
   
10.     else:
    
11.         # 初始化一个素数列表
    
12.         l_pn = [2, 3]
    
13.         n = 3
    
14.         # 循环遍历，判断是否为素数
    
15.         while len(l_pn) < number:
    
16.             n += 2
    
17.             # 标志位
    
18.             ispm = True
    
19.             sqr_n = int(sqrt(n))
    
20.             for t in l_pn:
    
21.                 if n % t == 0:
    
22.                     ispm = False
    
23.                     break
    
24.                 if t > sqr_n:
    
25.                     break               
    
26.             if ispm:
    
27.                 l_pn.append(n)               
    
28.         return l_pn
    
29.    
    
30. number = int(input('请输入要查找的数值：'))   
    
31. start = time()
    
32. print('第 %d 个素数是: %d' % (number, max(findNPrimes(number))))
    
33. print('cost %.3f sec' % (time() - start))
    
34. 
    

复制代码

第 10001 个素数是: 104743
cost 0.135 sec

渡风

此代码使用matlab编程
Problem7所用时间为1.1085秒
Problem7的答案为104743

1. %题目7：找出第10001个质数
   
2. function Output=Problem7(Input)
   
3. if nargin==0
   
4.     Input=10001;
   
5. end
   
6. tic
   
7. Sum=0;
   
8. Start=1;
   
9. while (Sum<Input)
   
10.     Start=Start+1;
    
11.     Judge=Prime_Judge(Start);
    
12.     if Judge==1
    
13.         Sum=Sum+1;
    
14.     end
    
15. end
    
16. Output=Start;   
    
17. toc
    
18. disp('此代码使用matlab编程')
    
19. disp(['Problem7所用时间为',num2str(toc),'秒'])
    
20. disp(['Problem7的答案为',num2str(Output)])
    
21. end
    
22. %% 子程序
    
23. %验证其是否为素数
    
24. %若输入为素数则Judge为1，否则为0
    
25. function Judge=Prime_Judge(Input)
    
26. if Input==2
    
27.     Judge=1;
    
28. else
    
29.     node=floor(sqrt(Input))+1;
    
30.     Judge=1;
    
31.     for ii=2:node
    
32.         if  mod(Input,ii)==0
    
33.             Judge=0;
    
34.             break
    
35.         else
    
36.         end
    
37.     end
    
38. end  
    
39. end

复制代码

FlySelf

1. import time
   
2. 
   
3. def is_prime(number):
   
4.     '判断是否为质数'
   
5.     flag = True
   
6.     for i in range(2, int(number ** 0.5) + 1):
   
7.         if number % i == 0:
   
8.             flag = False
   
9.     return flag
   
10. 
    
11. def find_prime(number=1):
    
12.     '寻找第number个质数'
    
13.     prime = 1
    
14.     i = 1
    
15.     while i < number:
    
16.         prime += 2
    
17.         if is_prime(prime):
    
18.             i += 1
    
19.     return prime
    
20. 
    
21. start = time.clock()
    
22. print('第10001个质数为%d' %find_prime(10001))
    
23. end = time.clock()
    
24. print('程序执行了%fs。' %(end - start))
    

复制代码

执行结果：
第10001个质数为104743
程序执行了1.150654s。

piperacillin

1. def ifprime(n):
   
2.     k = 0
   
3.     if n == 1 or n == 0:
   
4.         k = 1
   
5.     elif n % 2 == 0 and n != 2:
   
6.         k = 1
   
7.     else:
   
8.         from math import sqrt
   
9.         maxi = int(sqrt(n))
   
10.         for i in range(3,maxi+1,2):
    
11.             if n % i == 0:
    
12.                 k = 1
    
13.                 break
    
14.     if k == 0:
    
15.         return True
    
16.     if k == 1:
    
17.         return False
    
18. 
    
19. 
    
20. i = 1
    
21. j = 1
    
22. while True:
    
23.     j +=2
    
24.     if ifprime(j):
    
25.         i +=1
    
26.     if i== 10001:
    
27.         print(j)
    
28.         break
    

复制代码

104743 平均运行时间0.2s

0mrli0

1. /*题目：求第10001个质数*/
   
2. #include <stdio.h>
   
3. #include <math.h>
   
4. 
   
5. int IsPrime(int x)
   
6. {
   
7.         int i, flag;
   
8.         flag = 1;
   
9.         for (i=2; i<=(int)sqrt(x); i++)
   
10.         {
    
11.                 if (x%i == 0)
    
12.                 {
    
13.                         flag = 0;
    
14.                         break;
    
15.                 }
    
16.         }
    
17.         return flag;
    
18. }
    
19. 
    
20. int main()
    
21. {
    
22.         int i = 1;  //存放结果
    
23.         int n = 0;  //数目
    
24.         while (n<10002)
    
25.         {
    
26.                 i++;
    
27.                 n = IsPrime(i) ? n+1 : n;
    
28.         }
    
29.         printf("第10001个质数是： %d \n", i);
    
30.         return 0;
    
31. }

复制代码

第10001个质数是： 104759

Process returned 0 (0x0)   execution time : 0.177 s

余欲渔

这题要是算法不好不知道跑多久，我这效率应该还是不错的

1. zs=[2,3]
   
2. i=5
   
3. def zzz(i):
   
4.     for x in zs:
   
5.         if i%x==0:
   
6.             return 0
   
7.     return 1
   
8. while True:
   
9.     if zzz(i):
   
10.         zs.append(i)
    
11.     i+=2
    
12.     if len(zs)>10000:
    
13.         print(zs[10000])
    
14.         break
    

复制代码

1. == RESTART: C:\Users\ASUS\AppData\Local\Programs\Python\Python35-32\test.py ==
   
2. 104743
   
3. >>>

复制代码

夜魔时生

1. m=3
   
2. n=1
   
3. while True:
   
4.     for i in range(2,m):
   
5.         if m%i==0:
   
6.             break
   
7.     else:
   
8.         n+=1
   
9.     if n==10001:
   
10.         print(m)
    
11.         break
    
12.     m+=1

复制代码

99592938

1. import time
   
2. start = time.clock()
   
3. list_prime=[2,3]
   
4. num=5
   
5. a=2
   
6. while 1:
   
7.     ret=1
   
8.     for i in range(2,int(num**0.5)+1):
   
9.         if num%i ==0:
   
10.             ret=0
    
11.             break
    
12.     if ret:
    
13.         list_prime.append(num)
    
14.         a+=1
    
15.     if a==10001:
    
16.         print(num)
    
17.         break
    
18.     num+=2
    
19. end = time.clock()
    
20. print("read:%f s" %(end - start))

复制代码

104743
read:0.803580 s

99592938

99592938 发表于 2017-3-14 16:07
104743
read:0.803580 s

list_prime其实不用加进来，但发现几乎没有降低运行效率，就写上了，毕竟万一让输出1万个质数呢

JonTargaryen

The 10001st prime is: 104743

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int is_prime(long);
   
5. 
   
6. int main(void)
   
7. {
   
8.     long num = 3;
   
9.     int count = 2;
   
10. 
    
11.     while(count < 10001)
    
12.     {
    
13.         num += 2;
    
14. 
    
15.         if(is_prime(num))
    
16.         {
    
17.             count++;
    
18.         }
    
19.     }
    
20. 
    
21.     printf("The %dst prime is: %ld\n", count, num);
    
22. 
    
23.     return 0;
    
24. }
    
25. 
    
26. int is_prime(long num)
    
27. {
    
28.     long i;
    
29. 
    
30.     for(i = 2; i <= sqrt(num); i++)
    
31.     {
    
32.         if(!(num % i))
    
33.         {
    
34.             return 0;
    
35.         }
    
36.     }
    
37. 
    
38.     return 1;
    
39. }
    

复制代码

JonTargaryen

JonTargaryen 发表于 2017-3-28 14:17
The 10001st prime is: 104743

1. import math
   
2. 
   
3. def is_prime(num):
   
4.     for i in range(2, int(math.sqrt(num)) + 1 ):
   
5.         if not (num % i):
   
6.             return 0
   
7. 
   
8.     return 1
   
9. 
   
10. def main():
    
11.     num = 3
    
12.     count = 2
    
13. 
    
14.     while count < 10001:
    
15.         num += 2
    
16. 
    
17.         if is_prime(num):
    
18.             count += 1
    
19. 
    
20.     print("The 10001st prime is:", num)
    
21. 
    
22. if __name__ == "__main__":
    
23.     main()

复制代码