题目7：找出第10001个质数

Plusenxue

n = 1
temp = [2]
value = 3
while n <= 10000:
    for i in temp:
        if value%i == 0:
            break
        if i == temp[-1]:
            temp.append(value)
            n += 1

    value += 1

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

def euler(x):
    count = 0
    number = 2
    while count < x:
        if number == 2:
            number += 1
            count += 1
            continue
        for i in range(2,number):
            if not number%i:
                break
        else:
            count += 1
        number += 2
    return number - 2

if __name__ == '__main__':
    print(euler(10001))

镜中人31

i = 5
j = 2
list1 = [2,3]
while True:
    for k in list1[1:]:
        if(i%k == 0):
            break
        if k == list1[j-1]:
            list1.append(i)
            j += 1
    if j == 10001:
        break
    i += 2
print(i)

我的20来秒时间，答案104743

tsembrace

import time
import math

start=time.clock()
def isPrime(n):
    if n<2:
        return False
    elif n==2:
        return True
    else:
        m=int(math.sqrt(n))
        for i in range(2,m+1):
            if n%i==0:
                return False
        return True

count=0
i=2
while count<10001:
    if isPrime(i):
        count+=1
        i+=1
        continue
    else:
        i+=1

print(i-1)
end=time.clock()
print("耗时"+str(end-start)+"s")
        

toBeNot

public class The10001Prime {
        public static boolean isPrime(int n){
                boolean flag = true;
                for(int i = 2;i < n;i++){
                        if(n % i == 0){
                                flag = false;
                                break;
                        }
                }
                return flag;
        }
        public static void main(String[] args){
                int number = 1;
                int j = 0;
                for(j = 3;number < 10001;j = j +2){
                        if(isPrime(j)){
                                number += 1;
                        }
                }
                System.out.println("第10001个质数是：" + (j - 2));        
        }
}

梦想绘制者

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

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

梦想绘制者

# Python 3.5实现求第10001个质数
def isPrime(n):
    if n <= 1:
        return False
    else:
        half = int(n ** 0.5) # n // 2
        for i in range(2,half + 1):
            if n % i == 0:
                return False
        return True

def nthPrime(nth):
    primeCount = 0
    num = 1
    while 1:
        num += 1
        if isPrime(num):
            primeCount += 1
        else:
            continue
        if primeCount == nth:
            return num

nth = 10001
print('第%d个质数为%d'%(nth, nthPrime(nth)))

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

lyciam

t = time.clock()

def isprime(n):
    if (n%2==0 and n!=2) or n==1: return False
    for x in range(3,int(math.sqrt(n))+1,2):
        if n%x==0 or n%5==0: return False
    else: return True

def euler07(num=10001):
    """第10001个质数是多少？"""
    count = 0
    n = 0
    while count<num:
        n += 1
        if isprime(n): count+=1
    return {count:n}

print(euler07(10001),'time:',time.clock()-t)

{10001: 104743} time: 0.45091703770432073

芒果加黄桃

# encoding:utf-8
from math import sqrt
from time import time
      
def findNPrimes(number):
    if number == 1:
        return [2]
    elif number == 2:
        return [2, 3]
    else:
        # 初始化一个素数列表
        l_pn = [2, 3]
        n = 3
        # 循环遍历，判断是否为素数
        while len(l_pn) < number:
            n += 2
            # 标志位
            ispm = True
            sqr_n = int(sqrt(n))
            for t in l_pn:
                if n % t == 0:
                    ispm = False
                    break
                if t > sqr_n:
                    break                
            if ispm:
                l_pn.append(n)                
        return l_pn 
    
number = int(input('请输入要查找的数值：'))    
start = time()
print('第 %d 个素数是: %d' % (number, max(findNPrimes(number))))
print('cost %.3f sec' % (time() - start))

第 10001 个素数是: 104743
cost 0.135 sec

渡风

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

%题目7：找出第10001个质数 
function Output=Problem7(Input)
if nargin==0
    Input=10001;
end
tic
Sum=0;
Start=1;
while (Sum<Input)
    Start=Start+1;
    Judge=Prime_Judge(Start);
    if Judge==1
        Sum=Sum+1;
    end
end
Output=Start;    
toc
disp('此代码使用matlab编程')
disp(['Problem7所用时间为',num2str(toc),'秒'])
disp(['Problem7的答案为',num2str(Output)])
end
%% 子程序
%验证其是否为素数
%若输入为素数则Judge为1，否则为0
function Judge=Prime_Judge(Input)
if Input==2
    Judge=1;
else
    node=floor(sqrt(Input))+1;
    Judge=1;
    for ii=2:node
        if  mod(Input,ii)==0
            Judge=0;
            break
        else
        end
    end
end  
end

FlySelf

import time

def is_prime(number):
    '判断是否为质数'
    flag = True
    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0:
            flag = False
    return flag

def find_prime(number=1):
    '寻找第number个质数'
    prime = 1
    i = 1
    while i < number:
        prime += 2
        if is_prime(prime):
            i += 1
    return prime

start = time.clock()
print('第10001个质数为%d' %find_prime(10001))
end = time.clock()
print('程序执行了%fs。' %(end - start))

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

piperacillin

def ifprime(n):
    k = 0
    if n == 1 or n == 0:
        k = 1
    elif n % 2 == 0 and n != 2:
        k = 1
    else:
        from math import sqrt
        maxi = int(sqrt(n))
        for i in range(3,maxi+1,2):
            if n % i == 0:
                k = 1
                break
    if k == 0:
        return True
    if k == 1:
        return False


i = 1
j = 1
while True:
    j +=2
    if ifprime(j):
        i +=1
    if i== 10001:
        print(j)
        break

104743 平均运行时间0.2s

0mrli0

/*题目：求第10001个质数*/
#include <stdio.h>
#include <math.h>

int IsPrime(int x)
{
        int i, flag;
        flag = 1;
        for (i=2; i<=(int)sqrt(x); i++)
        {
                if (x%i == 0)
                {
                        flag = 0;
                        break;
                }
        }
        return flag;
}

int main()
{
        int i = 1;  //存放结果
        int n = 0;  //数目
        while (n<10002)
        {
                i++;
                n = IsPrime(i) ? n+1 : n;
        }
        printf("第10001个质数是： %d \n", i);
        return 0;
}

第10001个质数是： 104759

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

余欲渔

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

zs=[2,3]
i=5
def zzz(i):
    for x in zs:
        if i%x==0:
            return 0
    return 1
while True:
    if zzz(i):
        zs.append(i)
    i+=2
    if len(zs)>10000:
        print(zs[10000])
        break

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

夜魔时生

m=3
n=1
while True:
    for i in range(2,m):
        if m%i==0:
            break
    else:
        n+=1
    if n==10001:
        print(m)
        break
    m+=1

99592938

import time
start = time.clock()
list_prime=[2,3]
num=5
a=2
while 1:
    ret=1
    for i in range(2,int(num**0.5)+1):
        if num%i ==0:
            ret=0
            break
    if ret:
        list_prime.append(num)
        a+=1
    if a==10001:
        print(num)
        break
    num+=2
end = time.clock()
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

#include <stdio.h>
#include <math.h>

int is_prime(long);

int main(void)
{
    long num = 3;
    int count = 2;

    while(count < 10001)
    {
        num += 2;

        if(is_prime(num))
        {
            count++;
        }
    }

    printf("The %dst prime is: %ld\n", count, num);

    return 0;
}

int is_prime(long num)
{
    long i;

    for(i = 2; i <= sqrt(num); i++)
    {
        if(!(num % i))
        {
            return 0;
        }
    }

    return 1;
}

JonTargaryen

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

import math

def is_prime(num):
    for i in range(2, int(math.sqrt(num)) + 1 ):
        if not (num % i):
            return 0

    return 1

def main():
    num = 3
    count = 2

    while count < 10001:
        num += 2

        if is_prime(num):
            count += 1

    print("The 10001st prime is:", num)

if __name__ == "__main__":
    main()