鱼C论坛

 找回密码
 立即注册
楼主: 欧拉计划

题目7:找出第10001个质数

[复制链接]
发表于 2017-4-17 01:36:11 | 显示全部楼层
#求解第10001个素数

  1. import math
  2. import time

  3. start = time.time()

  4. def ifprime(n):
  5.         r = int(math.sqrt(n))
  6.         for i in range(2,r+1):
  7.             if n%i == 0:
  8.                 return 0
  9.         return 1


  10. count = 0
  11. number = 2
  12. while True:
  13.     if ifprime(number):
  14.         count += 1
  15.     if count == 10001:
  16.         print(number)
  17.         break
  18.     number += 1

  19. end = time.time()
  20. print(end-start)
复制代码


结果:104743
时间:0.5383784770965576
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-30 22:31:49 | 显示全部楼层
本帖最后由 天之南 于 2017-4-30 22:34 编辑
  1. #include<stdio.h>

  2. int main()
  3. {
  4.         const int L = 10001;
  5.         int arr[10001] = { 2 };
  6.         int i = 1;
  7.         for (int x = 3;i < L;x+=2)
  8.         {
  9.                 int j = 0;
  10.                 while (j < i && x % arr[j] != 0 && ++j);
  11.                 if (i == j) {
  12.                         arr[i] = x;
  13.                         i++;
  14.                 }
  15.         }
  16.         printf("%d\n", arr[L-1]);
  17. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-4 17:07:36 | 显示全部楼层
答案是104743

  1. #include<stdio.h>

  2. int main(void)
  3. {
  4.         int i=14,j,num=6;
  5.        
  6.         while(1)
  7.         {
  8.                 if(i%2==0)        goto Next_Num;
  9.                 for(j=3; j<=i/2 ;j+=2)        //这样可以减少大量冗余计算
  10.                 {
  11.                         if(i%j==0)        goto Next_Num;
  12.                 }
  13.                 num++;
  14.                 if(num==10001)        break;
  15.         Next_Num:
  16.                 ++i;
  17.         }
  18.         printf("第%d个素数是 %d\n",num,i);
  19.         return 0;
  20. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-7 16:09:44 | 显示全部楼层
  1. public static void main(String[] args) {
  2. //                7、前六个质数是2,3,5,7,11,13其中第6个是13.
  3. //                第10001个质数是多少?
  4.                 int i=1,j=3;
  5.                 while(i!=10001){
  6.                         while(true){
  7.                         if(cmp(j++)){
  8.                                 break;
  9.                         }
  10.                         }
  11.                         i++;
  12.                 }
  13.                 System.out.println(j-1);

  14.         }
  15.         public static boolean cmp(int num){
  16.                 for(int i=2;i<num;i++){
  17.                         if(num%i==0){
  18.                                 return false;
  19.                         }
  20.                 }
  21.                 return true;
  22.         }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-4 17:31:18 | 显示全部楼层
  1. import time

  2. def FindPrime(count):
  3.     '''获得第N个质数
  4.     ---由3开始累加2判断是否质数  初始化质数个数1
  5.     ---每出现一个质数个数prime_count+1

  6.     '''
  7.     prime_count = 1
  8.     number = 3
  9.     while 1:
  10.         flag = 0
  11.         r = (number + 1) // 2
  12.         for i in range(2,r+1):
  13.             if number%i == 0:
  14.                 flag = 1
  15.                 break
  16.         if flag == 0:
  17.             prime_count += 1
  18.         if prime_count == count:
  19.             break
  20.         number += 2
  21.     print(number)

  22. start = time.clock()
  23. FindPrime(10001)
  24. end = time.clock()
  25. print('耗时%f s'%(end - start))
复制代码


运行16s+、 学习下其他鱼友的思路看看 我的脑浆先这样了。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-4 17:47:22 | 显示全部楼层
始终 发表于 2016-8-12 19:11
答案:104743 运行时间最高0.9s

为什么判断是否质数 n%i  i范围<n的平方根啊啊啊啊啊啊
- -速度就差这边了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-4 17:50:39 | 显示全部楼层
        #r = (number + 1) // 2  运行速度 17.56s
        r = int(number ** 0.5)    运行速度 0.201s
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-2 10:24:09 | 显示全部楼层
  1. #找出第10001个质数是多少
  2. k=1
  3. num=2
  4. i=0
  5. pd=1
  6. while (k<10002):
  7.     if (num==2 or num==3):
  8.         #print (num,k)
  9.         k=k+1
  10.     else:
  11.         for i in range(2,(num+1)//2):
  12.             if (num%i==0):
  13.                 pd=0
  14.                 break
  15.         if (i ==(num+1)//2-1 and num!=6):
  16.             #print (num,k)
  17.             k=k+1
  18.     num=num+1
  19. print (num-1,k)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-11 17:27:47 | 显示全部楼层
  1. def check(n):
  2.     for i in range(2,n//2+1):
  3.         if not (n%i):
  4.             return False
  5.     return True

  6. result = 2
  7. count = 1
  8. while count < 10002:
  9.     if check(result):
  10.         count += 1
  11.     result += 1
  12.    
  13. print(result-1)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-29 17:19:37 | 显示全部楼层
AArdio编译:
  1. import console;
  2. import time.timer

  3. console.setTitle("test");

  4. time.timer.start();

  5. var is_prime = function(n){
  6.         if n%2==0 {
  7.                 return false
  8.         }
  9.         for i=3;n**0.5;2 {
  10.                 if n%i==0 {
  11.                         return false
  12.                 }
  13.         }
  14.         return true
  15. }

  16. var tab = {2;}
  17. p = 3
  18. while #tab<10001 {
  19.         if is_prime(p) {
  20.                 table.push(tab,p)
  21.         }
  22.         p += 2
  23. }
  24. console.print(table.pop(tab));

  25. console.print(time.timer.endTick(), '毫秒');
  26. console.pause();
  27. console.close()
复制代码

104743
70.252956390381 毫秒
请按任意键继续 ...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-1-4 16:25:43 | 显示全部楼层
答案 104743
#include <stdio.h>
#include <math.h>

int isprem( int n)
{
        int i;
        for(i=2; i<=sqrt(n); i++)
        {
                if (n%i==0)
                {
                        return 0;
                }
        }
       
        return 1;
}

int main(void)
{
        int count=0;
        int n=2;
       
        while (count!=10001)
        {
                if(isprem(n))
                {
                        count++;
                 }
                 n++;
         }
         
         printf("%d",--n);
       
        return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-1-10 17:24:08 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>

  4. int isPrimer(int n)
  5. {
  6.     int i;
  7.     for(i=2;i<=sqrt(n);i++){
  8.         if(n % i == 0){
  9.             return 0;
  10.         }
  11.     }
  12.     return 1;
  13. }

  14. int main()
  15. {
  16.     int n = 2,s=0;

  17.     for(;;n++){
  18.         if(isPrimer(n)){
  19.             s++;
  20.         }
  21.         if(s==10001){
  22.             break;
  23.         }
  24.     }
  25.     printf("%d\n",n);
  26.     return 0;
  27. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-27 14:30:22 | 显示全部楼层
  1. def isPrime(num):
  2.     if num == 2:
  3.         return True
  4.     elif num < 2 or num % 2 == 0:
  5.         return False
  6.     else:
  7.         for i in range(3, int(num ** 0.5) + 1, 2):
  8.             if num % i == 0:
  9.                 return False
  10.         else:
  11.             return True


  12. num = 1
  13. count = 0
  14. while True:
  15.     if isPrime(num):
  16.         count += 1
  17.     if count == 10001:
  18.         print num
  19.         break
  20.     num += 1
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-14 20:48:50 | 显示全部楼层
  1. import math
  2. # 判断n是否质数
  3. def prime(n):
  4.         flag=True # flag=True表示n是质数,False表示n是合数
  5.         # 当n=2时本应分开讨论,但因为flag一开始就是True,所以不影响结果
  6.         for i in range(2,int(math.sqrt(n))+1):
  7.                 # 任意一个数能整除n,则n是合数
  8.                 if n%i==0:
  9.                         flag=False
  10.                         break
  11.         if flag:
  12.                 return True # n是质数则返回True
  13.         else:
  14.                 return False # n是合数则返回False

  15. i=1 # i表示质数的序列编号。第1个质数是2,从第2个质数3开始计数,因此i初始值设为1
  16. n=1
  17. while i<10001:
  18.         n+=2 # 排除所有偶数
  19.         # 若n是质数,则质数序列编号i+1
  20.         if prime(n):
  21.                 i+=1
  22.        
  23. print ('第10001个质数是:%d'%n)
复制代码

结果是104743
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-26 00:19:01 | 显示全部楼层
  1. //运行时间四秒之内
  2. //题目:找出第10001个质数
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. int main()
  6. {
  7.      int   i;   //循环计数变量
  8.      int   j;    //质数变量
  9.      int   temp;    //质数个数变量
  10.      for (temp=0;temp<10001;   )
  11.       {
  12.            for (i=2;i<j;i++)
  13.              {
  14.                   if(j%i !=0)
  15.                           ;
  16.                     else  break;
  17.                 }
  18.              if(    j==i   )
  19.                 temp++  ;   //此时temp加一的值为10001所以此时J为所求的质数
  20.                 j++;       //最后结果多算了一次,所以输出时结果要减一。
  21.           }
  22.            printf("%d是第10001个质数",j-1);
  23.             return  0;
  24. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-26 00:22:49 | 显示全部楼层

答案也是:104743
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-6 17:05:59 | 显示全部楼层
  1. #找出第10001个质数
  2. import time
  3. import math

  4. def iszs(x):
  5.     k=1
  6.     if x == 2:
  7.         return True
  8.     else:
  9.         if 2<x<10:
  10.             for i in range(2,x):
  11.                 b= x%i
  12.                 if b == 0:
  13.                     return False
  14.                 else:
  15.                     continue
  16.             return True  
  17.         else:
  18.             a = int(math.sqrt(x))+1
  19.             for i in range(2,a):
  20.                 b = x%i
  21.                 if b == 0:
  22.                     return False
  23.                 else:
  24.                     continue
  25.             return True
  26. def getlist(x):
  27.     i = 2
  28.     list_zs=[]
  29.     while 1:
  30.         if iszs(i) == True:
  31.             list_zs.append(i)
  32.             #print(list_zs)
  33.             if len(list_zs) == x:
  34.                 return list_zs[x-1]
  35.         i+=1   
  36.    
  37.             
  38. def main():
  39.     starttime = time.time()
  40.     print(getlist(10001))
  41.     endtime = time.time()
  42.     print(endtime-starttime)
  43. if __name__=="__main__":
  44.     main()
复制代码



python,用时0.2秒,104743
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-14 17:12:08 | 显示全部楼层
import math
def judgePrimes(num):               #素数的判断方法
    if num % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(num))+1, 2):
        if not num % i:
            return False
    else:
        return True
   
def the10001Primes():
    i, j = 3, 1
    while j<10001:
        if judgePrimes(i):
            j +=1
        i +=2
    i -=2
    print('第1001个素数是:%d' % i)
        
the10001Primes()

答案:104743 运行时间3秒左右
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-14 17:21:54 | 显示全部楼层
import math
def judgePrimes(num):               #素数的判断方法
    if num % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(num))+1, 2):
        if not num % i:
            return False
    else:
        return True
   
def the10001Primes():
    i, j = 3, 1
    while j<10001:
        if judgePrimes(i):
            j +=1
        i +=2
    i -=2
    print('第1001个素数是:%d' % i)
   
import time
start = time.clock()        
the10001Primes()   
end = time.clock()
print(end-start)

答案: 104743  运行时间0.6秒左右
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-22 19:26:24 | 显示全部楼层
  1. #include<stdio.h>
  2. #include<math.h>
  3. long int prime(long int x);
  4. long int nextprime(long int x);
  5. int main()
  6. {
  7.     int i=1;
  8.     int primenumber=2;
  9.     while(i<10001){
  10.         primenumber=nextprime(primenumber);
  11.         printf("nextprime=%d\n",primenumber);
  12.         i++;
  13.     }
  14.     printf("%d\n",primenumber);
  15. }
  16. long int prime(long int x)
  17. {
  18.     long int i=2;
  19.     long int y;
  20.     y=sqrt(x);
  21.     if(x==1)
  22.         return 0;
  23.     for(i=2;i<=y;i++){
  24.         if(x%i==0){
  25.             return 0;
  26.         }
  27.     }
  28.     return 1;
  29. }
  30. long int nextprime(long int x)
  31. {
  32.     x+=1;
  33.     while(1){
  34.         if(prime(x)){
  35.             return x;
  36.         }
  37.         x++;
  38.     }
  39. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 01:01

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表