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