题目7：找出第10001个质数

xuan1788

"""
To find the nth prime
"""
import math
from math import sqrt, floor

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

def getNthPrime(n):
    x = 2
    if n == 1:
        return 2
    if n == 2:
        return 3
    p = 3
    while x < n:
        p += 2
        if is_prime(p):
            x += 1
    return p

yhhpf

flag = 1
a = 1
b = 1
while flag:
    a += 2
    c = 3
    while c <= a ** 0.5 :
        if a % c == 0:
            break
        c += 2
    if c > a**0.5:
        b += 1
    if b == 10001:
        flag = 0
print(a)

4444567

from time import time
from math import sqrt

def prime(x):
    if x <= 2:
        print('error')
    else:
        if x%2 == 0:
            return False
        for i in range(3,int(sqrt(x))+1,2):
            if  x%i == 0:
                return False
        return x
    
t1 = time()       
m = [2,3,5,7,11,13]
i = 14
while True:
    if prime(i):
        m.append(i)
    if len(m) == 10001:
        print(m[-1])
        break
    i += 1
 
t2 = time()
t=t2-t1
print('耗时为：%s' % t)    

有马_冬巳

'''前六个质数是 2, 3, 5, 7, 11 和 13，其中第 6 个是 13。
第 10001 个质数是多少？'''

def numprime(position):
    a = 8
    prime_sequence = [2,3,5,7]
    while len(prime_sequence) < position:
        for prime in range(2,int(a/2)):
            check = 0
            if a%prime == 0:
                check += 1
                break
        if check == 0:
            prime_sequence.append(a)
        a += 1
    print("第%d个质数是: %d" %(position,prime_sequence[position-1]))

start_numprime = time.time()
numprime(10001)
time_numprime = time.time() - start_numprime
print("%f秒" %time_numprime)

第10001个质数是: 104743
17.688404秒

gonorth

import math as m


def is_prime(n):
    if n > 1:
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        for each in range(3, int(m.sqrt(n )) + 1, 2):
            if n % each == 0:
                return False
        return True
    return False


def get_prime(n):
    while 1:
        if is_prime(n):
            yield n
        n = n + 1


def solve():
    count = 0
    for i in get_prime(1):
        count = count + 1
        if count + 1> 10001:
            break
    return i


print(solve())

a1351468657

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

main()
{
        int count = 0, num, i, j = 2, flag = 1;
        while (1)
        {
                for (i = 2; i < sqrt(j + 1); i++)
                {
                        if (j % i == 0)
                        {
                                flag = 0;
                        }
                }
                if (flag == 1)
                {
                        count++;
                }
                if (count == 10001)
                {
                        printf("\n第100001个质数是：%d\n", j);
                        break;
                }
                j++;
                flag = 1;
        }
}

老师帮我看看效率怎样，基本秒出答案， 104743

永恒的蓝色梦想

a1351468657 发表于 2021-3-6 15:38
老师帮我看看效率怎样，基本秒出答案， 104743

如果没开优化, 第9行的判断条件会不断调用sqrt, 严重浪费性能。
质数筛法会比普通的判断质数快。

Kuri5u

flag=True
result=2
time=2
i=5
while time<=10001:
    for each in range (2,i//2+1):
        if i % each == 0:
            flag=0
            i+=1
            break
    if flag:
        result=i
        time+=1
        i+=1
    else:
        flag=1
print(result)

104743

卢本伟牛逼

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

int count = 0;

int is_prime(int value)
{
        int i=2;
        for(i;i<sqrt(value);i++)//改进1 
        {
                count += 1;
                if (i>3) i++; //改进2 
                if (value % i == 0) return 0;
        }
        return 1;
}

int main(void)
{
        int flag = 1;
        int i = 3;
        while(1)
        {
                if (is_prime(i)) flag += 1;
                if (flag >= 10001) break;
                i += 2;//改进3 
        }
        
        printf("result = %d\n", i);
        printf("count = %d\n", count);//count = 1491484 
        return 0;
 } 

鱼塘里的鱼儿

#include <iostream>
using namespace std;
int main()
{
        int sum=0,i=2;
        for(;;i++)
        {
         for(int i1=2;i1<i;i1++)
         {
                 if(i%i1==0)
                         break;
                 if(i1==(i-1))
                         sum++;
         }
         if(sum==10001)
         {
                 cout<<i<<endl;
                 break;
         }
        }
        return 0;
}

\\C++写的答案：104759

ft215378

#生成输入值范围内的素数（质数）返回列表
from math import *
#判断是否是素数
def is_prime(number):
    if number > 1:
        if number == 2:
            return True
        if number % 2 == 0:
            return False
        for a in range(3,int(sqrt(number) + 1),2):
            if number % a == 0:
                return False
        return True
    return False
#生成素数列表，得到num以内的素数（返回列表primelist）
primelist = []
num = 110000

while 1:
    for i in range(2, num + 1):
        if is_prime(i):
            primelist.append(i)
            if len(primelist) == 10000:
                break

   
    break



   

番杰

#include<stdio.h>

int mian(void)
{
        int result,flag = 0 ,num = 6;
        
        for(int i = 13;;i++)
        {
                 for(int j = 2;j<(i/2);j++)
                 (
                        if(i / j == 0)
                        {
                                flag = 1;
                                break;
                        } 
                )
                
                if(flag == 1)
                        flag = 0;
                else
                {
                        num++;
                        if(num == 10001)
                        {
                                result = i;
                                break;
                        }
                }
        }
        
        printf("%d",result;
        
        return 0； 
} 

guosl

这个题目的大多数解都是通过整除性质来判断一个整数是否是一个素数，但这会耗费大量的时间，在此我用了筛法，时间大大地缩短了。

/*
答案：104743
耗时：0.0006446秒
*/
#include <iostream>
#include <cstring>
using namespace std;

const int N = 200004;

char cp[N];

int main(void)
{
  memset(cp + 2, 1, sizeof(char) * (N - 2));
  for (int i = 2; i <= 447; ++i)
  {
    if (cp[i] == 0)
      continue;
    for (int j = i * i; j <= N - 4; j += i)
      cp[j] = 0;
  }
  int nCount = 1;
  for (int i = 3; i <= N - 4; i += 2)
  {
    if (cp[i] == 1)
    {
      ++nCount;
      if (nCount == 10001)
      {
        cout << i << endl;
        break;
      }
    }
  }
  return 0;
}

mathtimes

2.1s

prime = [2,3]
i = 4
while len(prime)<10001:
    s = True
    for j in prime:
        if i%j == 0:
            s = False
            break
    if s:
        prime.append(i)
    i = i + 1
print(prime[-1])

0.5s

#include <stdio.h>
#include <vector>
using std::vector;
int main()
{
    vector<long long> prime;
    vector<long long>::iterator it;
    long long i;   
    prime.push_back(2);
    for(i=2;i<__LONG_LONG_MAX__&&prime.size()<10001;i++)
    {
        for(it=prime.begin();it!=prime.end();it++)
        {
            if(i%*it==0)
                goto loop;
        }
        prime.push_back(i);  
        loop:;
    }         
    printf("%lld",*(prime.end()-1));
}

Kazimierz

结果104759

#include <stdio.h>
#define NUM 10001

int main()
{
        int i,n=0,s=0,x=3;
        
        while(s<NUM)
        {
                for(i=2;i<x;i++)
                {
                        if(x%i==0){
                                n++;
                                x++;
                                break;
                        }
                }
                
                if(n==0){
                        s++;
                        x++;
                        continue;
                }
                
                n=0;
        }
        printf("%d",x-1);
        return 0;
        
}

jerryxjr1220

冗余设计用了长度1000000的列表，如果只考虑20万左右的列表，可以再缩小5倍的时间。

package main

import (
        "fmt"
        "time"
)

//题目6：
//
//前六个质数是 2, 3, 5, 7, 11 和 13，其中第 6 个是 13。
//
//第 10001 个质数是多少？
func main() {
        t := time.Now()
        var nums [1000000]int
        nums[0] = 1
        nums[1] = 1

        for i := 2; i < 1000; i++ {
                var j int
                for j = i * i; j < 1000000; j += i {
                        nums[j] = 1
                }
        }
        var c int = 0
        var count int = 0
        for c = 2; c < 1000000; c++ {
                if nums[c] == 0 {
                        count++
                }
                if count == 10001 {
                        fmt.Println(c)
                        break
                }
        }
        tt := time.Now()
        fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}

输出：

C:\Users\Anaconda\GolandProjects\EulerProject\output\go_build_Euler06_go.exe
104743
耗时： 19 ms

进程 已完成，退出代码为 0

Go语言还真是快

Asss-whom

这种暴算的任务Rust + Rayon轻松解决：
（抄的RustCC的代码）

use rayon::prelude::*;
use std::time::Instant;

const N: i32 = 200000;

fn main() {
    let now = Instant::now();
    let mut primes = Vec::new();
    let mut cur = 10;
    // bootstrap
    for i in 2..cur {
        if primes.iter().all(|p| i % p != 0) {
            primes.push(i);
        }
    }
    while cur < N {
        let next = std::cmp::min(cur * cur, N);
        let mut addition: Vec<_> = (cur..next)
            .into_par_iter()
            .filter(|x| {
                for p in primes.iter() {
                    if x % p == 0 {
                        return false;
                    }
                    if x / p < *p {
                        break;
                    }
                }
                true
            })
            .collect();
        primes.append(&mut addition);
        cur = next;
    }
    println!("{}", primes[10001]);
    println!("耗时{}毫秒。", now.elapsed().as_millis())
}

---
104759
耗时3毫秒。

歌者文明清理员

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

https://fishc.com.cn/thread-52272-1-1.html

Eca

#include <stdio.h>

int main() {
        long long int i = 1, num = 0, j = 0;
        while (num < 10001) {
                for ( j = 2; j < i; j++) {
                        if (i % j == 0)
                                break;
                }
                if (j == i)
                        num++;
                i++;
        }

        printf("%d", i - 1);
}

感觉写的一般，应该有更好的方法