论坛 › 欧拉计划（Project Euler） › 题目7：找出第10001个质数

欧拉计划 发表于 2015-4-20 23:53:35

题目7：找出第10001个质数

本帖最后由 不二如是 于 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 个质数是多少？

翅膀团 发表于 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;
       }
    }
}

如果有错误希望指出

无名侠 发表于 2015-7-11 23:33:00

104759 对吗？ 破电脑，跑了几分钟。

def prime (x):
      if x<=1:
                return False
      for j in range(2,x):
                if not(x%j):
                        returnFalse
      return True
def find1():
        i=13
        x=6
        while x<=10001:
                i+=1
                if prime(i):
                        x+=1
                        print(x,"   ",i)
        return i

牡丹花下死做鬼 发表于 2015-7-19 21:52:05

翅膀团 发表于 2015-7-3 17:00
#include

void main()


你运行试试看

牡丹花下死做鬼 发表于 2015-7-19 21:54:41

无名侠 发表于 2015-7-11 23:33
104759 对吗？ 破电脑，跑了几分钟。

我用C写的效率不高为了写代码快点但也是秒出答案了   104743
#include<stdio.h>
#include<math.h>
int Prime (long int j) //定义Prime函数判断是否为质数
{
        int i,k = 0;
        for(i = 2;i<=sqrt(j);++i)
        {
                if(j%i==0)
                {
                        k++;
                        break;
                }
        }
        if(k!=0)
        {
                return 0;
        }
        else
        {
                return 1;
        }
}
void main()
{
        int i = 1;
        long int j = 2;
        while(i!=10001) /*从二开始遍历发现是质数i自增1直到i=10001 也就找到了第10001个质数*/
        {
                ++j;
                if(Prime(j)==1)
                {
                        i++;
                }
        }
        printf("%ld\n",j);
}

翅膀团 发表于 2015-7-20 15:22:10

牡丹花下死做鬼 发表于 2015-7-19 21:52
你运行试试看

有哪里错了{:9_241:}

wyc1gg 发表于 2015-10-8 18:14:13

PYthon写的跑了一分钟差不多，结果：104743
感觉是不是算法简单导致循环次数过多？

maoguy 发表于 2015-11-4 16:04:30

/*题目7：找出第10001个质数*/

#include <iostream>

using namespace std;


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

int main ()

{
        long a; //数字
        long i;        //序数

        for(i = 1,a = 2;i <= 10001; a ++)
        {
                if (Prime(a) == 1) //判断a是否为素数
                {
                        i ++;
                }
                else
                {
                        continue;
                }


        }

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

        cout<<"第10001个质数为："<<a<<endl;
       

        return 0;
               
}

int Prime (long x)
{
        long i , k = 1;

        for(i = 2 ; i <= ( x / 2 ) ; i ++)
        {
                if (x % i == 0)
                {
                        k = 0;
                        break;
                }

                else
                {
                        continue;
                }
        }


        return k;

}
       

输出：第10001个质数为：104743

mysteri0n 发表于 2016-1-23 21:11:59

本帖最后由 mysteri0n 于 2016-1-23 21:13 编辑

#python 2.7.11

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

the_10001st = 0
for i in xrange(2,10**9):
        the_10001st += isprime(i)
        if the_10001st ==10001:
                print i
                break

zxc123qwe 发表于 2016-4-26 13:04:07

这代码怎么弄上去的，还能粘贴复制显示行数。教教我吧

zxc123qwe 发表于 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;}
        }
}

zxc123qwe 发表于 2016-4-26 20:52:08

zxc123qwe 发表于 2016-4-26 20:50
//我写的程序需要输入要找的第几个素数；i的值可以调整，运行不是太快，需要几秒，
#include



求大神指点指点

张无忌 发表于 2016-5-2 00:37:18

# -*- coding: utf-8 -*-
"""
10001st prime number.
"""
from math import sqrt, floor

def is_prime(number):
    if number > 1:
      if number == 2:
            return True
      if number%2 == 0:
            return False
      for i in range(3, floor(sqrt(number)) + 1, 2):
            if number%i == 0:
                return False
      return True
    return False

def find_prime():
    n = 2
    while True:
      if is_prime(n):
            yield n
      n += 1

fp = find_prime()

i, max_n = 1, 10001
while i < max_n:
    next(fp)
    i += 1

print(next(fp))

huomqh 发表于 2016-6-13 16:05:47

本帖最后由 huomqh 于 2016-6-13 16:07 编辑

i=1
list1=
z=1
while i<=10000:
    z+=2
    a=1
    for x in list1:
      if z%x == 0:
            a=0
            break
    if a:
      list1.append(z)
      i=i+1
print(z)

答案：104743

冷钟天 发表于 2016-7-6 09:08:10

a=
>>> i=13
>>> while len(a)!=10001:
        b=True
        i+=2
        for j in a:
                if i%j==0:
                        b=False
                        break
        if b:
                a.append(i)

幻世伽蓝 发表于 2016-7-8 21:14:30

n = 2
list_primer = []
def primer(x):
    for n in range(2,x + 1 // 2):
      if x % n == 0:
            return 0
    return x

while 1:
    if primer(n):
      list_primer.append(n)
    if len(list_primer) == 10001:
      break
    n += 1

print(max(list_primer))


不是秒出答案的一般打一把游戏就出结果了，跑了一分多钟~~

迷雾少年 发表于 2016-8-11 08:20:04

我这跑出104743
#include <iostream>
#include <stdlib.h>
using namespace std;
int main(void)
{

        int n=0,k=0,i;

        for ( i = 2; n<10001; i++)
        {
                for( k=2;k<i;k++)
                {
                        if(i%k==0&&k!=1)
                        {
                                break;
                        }
                }
                if(k==i){
                n++;
                cout<<i<<""<<n<<endl;
                }
       
        }
        //cout<<i<<endl;
        system("pause");
        return 0;
}

把        cout<<i<<""<<n<<endl;去掉大概2秒出答案

迷雾少年 发表于 2016-8-11 08:21:43

wyc1gg 发表于 2015-10-8 18:14
PYthon写的跑了一分钟差不多，结果：104743
感觉是不是算法简单导致循环次数过多？

我用c++写用最简单的算法跑2秒出来。。

迷雾少年 发表于 2016-8-11 08:22:57

无名侠 发表于 2015-7-11 23:33
104759 对吗？ 破电脑，跑了几分钟。

104759是10002个质数了。。

始终 发表于 2016-8-12 19:11:09

def is_prime(n):
    if n == 2:
      return True
    elif n % 2 == 0:
      return False
    i = 3
    while i <= n**0.5:
      if n % i == 0:
            return False
      i += 2
    return True


def getnth(n):
    if n == 1:
      return 2
    elif n == 2:
      return 3
    prime = 3
    x = 2
    while x < n:
      prime += 2
      if is_prime(prime):
            x += 1
    return prime
print(getnth(10001))

答案：104743 运行时间最高0.9s

查看完整版本: 题目7：找出第10001个质数