题目7：找出第10001个质数,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

xuan1788 发表于 2020-7-23 15:07:42

"""
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 发表于 2020-8-24 14:26:14

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 发表于 2020-8-30 21:37:23

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):
         ifx%i == 0:
            return False
   return x

t1 = time()
m =
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)

有马_冬巳 发表于 2020-10-4 10:12:25

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

def numprime(position):
a = 8
prime_sequence =
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))

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

第10001个质数是: 104743
17.688404秒

gonorth 发表于 2020-11-5 11:46:33

本帖最后由 gonorth 于 2020-11-5 11:51 编辑

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 发表于 2021-3-6 15:38:51

#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

永恒的蓝色梦想 发表于 2021-3-7 22:54:21

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

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

Kuri5u 发表于 2021-5-5 15:51:26

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

卢本伟牛逼 发表于 2021-8-9 00:45:26

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

鱼塘里的鱼儿 发表于 2021-10-7 22:03:09

#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 发表于 2021-10-9 13:21:23

#生成输入值范围内的素数（质数）返回列表
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

番杰发表于 2021-10-27 14:26:50

#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 发表于 2022-1-2 12:13:09

本帖最后由 guosl 于 2022-1-2 12:17 编辑

这个题目的大多数解都是通过整除性质来判断一个整数是否是一个素数，但这会耗费大量的时间，在此我用了筛法，时间大大地缩短了。/*
答案：104743
耗时：0.0006446秒
*/
#include <iostream>
#include <cstring>
using namespace std;

const int N = 200004;

char cp;

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

mathtimes 发表于 2022-1-28 20:45:14

本帖最后由 mathtimes 于 2022-2-12 11:38 编辑

2.1s
prime =
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 发表于 2022-2-22 17:03:20

结果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 发表于 2022-2-23 10:24:21

冗余设计用了长度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 int
nums = 1
nums = 1

for i := 2; i < 1000; i++ {
var j int
for j = i * i; j < 1000000; j += i {
nums = 1
}
}
var c int = 0
var count int = 0
for c = 2; c < 1000000; c++ {
if nums == 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语言还真是快{:5_109:}

Asss-whom 发表于 2022-8-7 21:52:42

本帖最后由 Asss-whom 于 2022-8-7 21:53 编辑

这种暴算的任务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);
println!("耗时{}毫秒。", now.elapsed().as_millis())
}

---
104759
耗时3毫秒。

歌者文明清理员 发表于 2023-2-18 12:01:13

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

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

Eca 发表于 2023-4-6 22:40:59

#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);
}
感觉写的一般，应该有更好的方法

页: 1 2 3 4 [5]

鱼C论坛's Archiver