鱼C论坛

 找回密码
 立即注册
查看: 13229|回复: 98

题目7:找出第10001个质数

[复制链接]
发表于 2015-4-20 23:53:35 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 不二如是 于 2017-6-9 07:02 编辑
10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?


题目:

前六个质数是 2, 3, 5, 7, 11 和 13,其中第 6 个是 13。

第 10001 个质数是多少?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-7-3 17:00:08 | 显示全部楼层
本帖最后由 翅膀团 于 2015-11-16 14:10 编辑

#include <stdio.h>

int main(void)
{
    int i,j,num;
    i = 1;
    num = 0;
    while(1)
    {
        i++;
        for(j=2;j<i;j++)
        {
            if(i % j ==0)
            {
            goto z;
            }
        }
        num++;
z:     j = 2;
       if(num == 10001)
       {
        printf("%d\n",i);
        return 0;
       }
    }
}

如果有错误希望指出
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 0 反对 1

使用道具 举报

发表于 2015-7-11 23:33:00 | 显示全部楼层
104759 对吗? 破电脑,跑了几分钟。

  1. def prime (x):
  2.         if x<=1:
  3.                 return False
  4.         for j in range(2,x):
  5.                 if not(x%j):
  6.                         return  False
  7.         return True
  8. def find1():
  9.         i=13
  10.         x=6
  11.         while x<=10001:
  12.                 i+=1
  13.                 if prime(i):
  14.                         x+=1
  15.                         print(x,"   ",i)
  16.         return i
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-19 21:52:05 | 显示全部楼层

你运行试试看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-19 21:54:41 | 显示全部楼层
无名侠 发表于 2015-7-11 23:33
104759 对吗? 破电脑,跑了几分钟。

我用C写的效率不高为了写代码快点但也是秒出答案了   104743
  1. #include<stdio.h>
  2. #include<math.h>
  3. int Prime (long int j) //定义Prime函数判断是否为质数
  4. {
  5.         int i,k = 0;
  6.         for(i = 2;i<=sqrt(j);++i)
  7.         {
  8.                 if(j%i==0)
  9.                 {
  10.                         k++;
  11.                         break;
  12.                 }
  13.         }
  14.         if(k!=0)
  15.         {
  16.                 return 0;
  17.         }
  18.         else
  19.         {
  20.                 return 1;
  21.         }
  22. }
  23. void main()
  24. {
  25.         int i = 1;
  26.         long int j = 2;
  27.         while(i!=10001) /*从二开始遍历发现是质数i自增1直到i=10001 也就找到了第10001个质数*/
  28.         {
  29.                 ++j;
  30.                 if(Prime(j)==1)
  31.                 {
  32.                         i++;
  33.                 }
  34.         }
  35.         printf("%ld\n",j);
  36. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-20 15:22:10 | 显示全部楼层

有哪里错了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-10-8 18:14:13 | 显示全部楼层
PYthon写的跑了一分钟差不多,结果:104743
感觉是不是算法简单导致循环次数过多?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-11-4 16:04:30 | 显示全部楼层
  1. /*题目7:找出第10001个质数*/

  2. #include <iostream>

  3. using namespace std;


  4. int Prime (long x);  //判断是否质数,是则返回1,否则返回0

  5. int main ()

  6. {
  7.         long a; //数字
  8.         long i;        //序数

  9.         for(i = 1,a = 2;i <= 10001; a ++)
  10.         {
  11.                 if (Prime(a) == 1) //判断a是否为素数
  12.                 {
  13.                         i ++;
  14.                 }
  15.                 else
  16.                 {
  17.                         continue;
  18.                 }


  19.         }

  20.         a -= 1; //上一步循环a自加1,这里减去1

  21.         cout<<"第10001个质数为:"<<a<<endl;
  22.        

  23.         return 0;
  24.                
  25. }

  26. int Prime (long x)
  27. {
  28.         long i , k = 1;

  29.         for(i = 2 ; i <= ( x / 2 ) ; i ++)
  30.         {
  31.                 if (x % i == 0)
  32.                 {
  33.                         k = 0;
  34.                         break;
  35.                 }

  36.                 else
  37.                 {
  38.                         continue;
  39.                 }
  40.         }


  41.         return k;

  42. }
  43.        
复制代码


输出:第10001个质数为:104743
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-1-23 21:11:59 | 显示全部楼层
本帖最后由 mysteri0n 于 2016-1-23 21:13 编辑
  1. #python 2.7.11

  2. def isprime(num):
  3.     for i in range(2,int(num**0.5)+1):
  4.         if num % i == 0:
  5.             return False
  6.     return True

  7. the_10001st = 0
  8. for i in xrange(2,10**9):
  9.         the_10001st += isprime(i)
  10.         if the_10001st ==10001:
  11.                 print i
  12.                 break
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-26 13:04:07 | 显示全部楼层
这代码怎么弄上去的,还能粘贴复制显示行数。教教我吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-26 20:50:54 | 显示全部楼层
//我写的程序需要输入要找的第几个素数;i的值可以调整,运行不是太快,需要几秒,
#include <stdio.h>

void main()
{
        int i,j,n=0,count=0,num;
        scanf("%d",&num);
        for(i=2;i<=1000000;i++)
        {   
                n=0;
                for(j=2;j<i;j++)
                {
                        if(i%j==0){
                        n=1;
                        break;
                        }
                }
                if(n==0) count+=1;
                if(count==num) {printf("找1000000以内第%d个素数是:%d",num,i);break;}
        }
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-26 20:52:08 | 显示全部楼层
zxc123qwe 发表于 2016-4-26 20:50
//我写的程序需要输入要找的第几个素数;i的值可以调整,运行不是太快,需要几秒,
#include

求大神指点指点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-5-2 00:37:18 | 显示全部楼层
  1. # -*- coding: utf-8 -*-
  2. """
  3. 10001st prime number.
  4. """
  5. from math import sqrt, floor

  6. def is_prime(number):
  7.     if number > 1:
  8.         if number == 2:
  9.             return True
  10.         if number%2 == 0:
  11.             return False
  12.         for i in range(3, floor(sqrt(number)) + 1, 2):
  13.             if number%i == 0:
  14.                 return False
  15.         return True
  16.     return False

  17. def find_prime():
  18.     n = 2
  19.     while True:
  20.         if is_prime(n):
  21.             yield n
  22.         n += 1

  23. fp = find_prime()

  24. i, max_n = 1, 10001
  25. while i < max_n:
  26.     next(fp)
  27.     i += 1

  28. print(next(fp))
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-6-13 16:05:47 | 显示全部楼层
本帖最后由 huomqh 于 2016-6-13 16:07 编辑
  1. i=1
  2. list1=[2]
  3. z=1
  4. while i<=10000:
  5.     z+=2
  6.     a=1
  7.     for x in list1:
  8.         if z%x == 0:
  9.             a=0
  10.             break
  11.     if a:
  12.         list1.append(z)
  13.         i=i+1
  14. print(z)
复制代码

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

使用道具 举报

发表于 2016-7-6 09:08:10 | 显示全部楼层
  1. a=[2,3,5,7,11,13]
  2. >>> i=13
  3. >>> while len(a)!=10001:
  4.         b=True
  5.         i+=2
  6.         for j in a:
  7.                 if i%j==0:
  8.                         b=False
  9.                         break
  10.         if b:
  11.                 a.append(i)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2016-7-8 21:14:30 | 显示全部楼层
  1. n = 2
  2. list_primer = []
  3. def primer(x):
  4.     for n in range(2,x + 1 // 2):
  5.         if x % n == 0:
  6.             return 0
  7.     return x

  8. while 1:
  9.     if primer(n):
  10.         list_primer.append(n)
  11.     if len(list_primer) == 10001:
  12.         break
  13.     n += 1

  14. print(max(list_primer))
复制代码


不是秒出答案的一般打一把游戏就出结果了,跑了一分多钟~~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-11 08:20:04 | 显示全部楼层
我这跑出104743
  1. #include <iostream>
  2. #include <stdlib.h>
  3. using namespace std;
  4. int main(void)
  5. {

  6.         int n=0,k=0,i;

  7.         for ( i = 2; n<10001; i++)
  8.         {
  9.                 for( k=2;k<i;k++)
  10.                 {
  11.                         if(i%k==0&&k!=1)
  12.                         {
  13.                                 break;
  14.                         }
  15.                 }
  16.                 if(k==i){
  17.                 n++;
  18.                 cout<<i<<"  "<<n<<endl;
  19.                 }
  20.        
  21.         }
  22.         //cout<<i<<endl;
  23.         system("pause");
  24.         return 0;
  25. }
复制代码


把        cout<<i<<"  "<<n<<endl;去掉大概2秒出答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-11 08:21:43 | 显示全部楼层
wyc1gg 发表于 2015-10-8 18:14
PYthon写的跑了一分钟差不多,结果:104743
感觉是不是算法简单导致循环次数过多?

我用c++写用最简单的算法跑2秒出来。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-11 08:22:57 | 显示全部楼层
无名侠 发表于 2015-7-11 23:33
104759 对吗? 破电脑,跑了几分钟。

104759是10002个质数了。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-8-12 19:11:09 | 显示全部楼层
  1. def is_prime(n):
  2.     if n == 2:
  3.         return True
  4.     elif n % 2 == 0:
  5.         return False
  6.     i = 3
  7.     while i <= n**0.5:
  8.         if n % i == 0:
  9.             return False
  10.         i += 2
  11.     return True


  12. def getnth(n):
  13.     if n == 1:
  14.         return 2
  15.     elif n == 2:
  16.         return 3
  17.     prime = 3
  18.     x = 2
  19.     while x < n:
  20.         prime += 2
  21.         if is_prime(prime):
  22.             x += 1
  23.     return prime
  24. print(getnth(10001))
复制代码

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

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-29 23:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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