题目7：找出第10001个质数

欧拉计划

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 个质数是多少？

翅膀团

#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;
       }
    }
}

如果有错误希望指出

无名侠

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

def prime (x):
        if x<=1:
                return False
        for j in range(2,x):
                if not(x%j):
                        return  False
        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-3 17:00
#include

void main()

你运行试试看

牡丹花下死做鬼

无名侠 发表于 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-19 21:52
你运行试试看

有哪里错了

wyc1gg

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

maoguy

/*题目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

#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

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

zxc123qwe

//我写的程序需要输入要找的第几个素数；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

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

求大神指点指点

张无忌

# -*- 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

i=1
list1=[2]
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

冷钟天

a=[2,3,5,7,11,13]
>>> 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)

幻世伽蓝

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))

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

迷雾少年

我这跑出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秒出答案

迷雾少年

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

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

迷雾少年

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

104759是10002个质数了。。

始终

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