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

zzzgod 发表于 2018-6-20 19:49:26

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
int count=1,num=3;
bool flag=1;
while(count!=10001)
{
for(int i=2;i<=sqrt(num);++i)
{
if(num%i==0)
{
flag=0;
}
}
if(flag==1)
{
++count;
}
flag=1;
++num;
}
cout<<--num;
}

塔利班 发表于 2018-8-24 08:42:25

def prime():
yield 2
x=3
while True:
   a=True
   for i in range(3,int(x**0.5)+1,2):
      if x%i==0:
            a=False
            break
   if a:
         yield x
   x+=2
a=prime()
for i in range(10001):
p=next(a)
print(p)

shanczp 发表于 2018-10-11 13:40:22

笨方法

void oula_7(void)
{
int num=2;
int i=0;
while (true)
{
int j=2;
while (true)
{
if(num%j==0)
{
if (num==j)
{
i++;
break;
}
break;
}
j++;
}
if (i==10001)break;
num++;
}
printf("%d\n",num);
}

山有扶苏啊 发表于 2018-10-12 13:34:54

跑了一分多钟，应该需要优化下

山有扶苏啊 发表于 2018-10-12 13:35:24

from math import sqrt

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

result = []
for t in range(1, 10000000):
if is_prime(t):
   result.append(t)
print(result

cupbbboom 发表于 2018-11-23 15:08:25

我自己写的，而且还是优化了很多遍。最短还要104s；结果大神（猜想应该是数学高手{:10_334:}），我把它贴出来的代码跑了下：1.0s；卧槽{:10_247:}；后面对比代码发现，大神在判断是否为质数时，全程用判断，而我全程for循环。而且，大神判断是否为质数那段代码我还想不通这个算法逻辑到底是个啥意思；下面贴出我和大神的代码对比：哎呀，我真是个辣鸡{:10_285:}
我的：
import time

判断质数
def isfrime(x): # 默认传入参数为大于1的整数，不判断了
t = True
# if x % 2 == 0 or x % 3 == 0 or x % 5 ==0 or x % 7 == 0:
# t = False
for i in range(2,x):
if x % i == 0:
t = False
break
return t

n = 8
count = 4
print('计算开始')
start_time = time.time()
while count < 10001:
if isfrime(n) == True:
count += 1
n += 1
result = n - 1 # 这是结果;减去当count=10001时，后面还增加的1
print('结果为：%s'%str(result))
end_time = time.time()
print('耗时：%s 秒'%str(end_time - start_time))

这是大神的：
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

import time
start_time = time.time()
print(getnth(10001))
end_time = time.time()
print('耗时：%s 秒'%str(end_time - start_time))

cupbbboom 发表于 2018-11-23 15:11:10

始终发表于 2016-8-12 19:11
答案：104743 运行时间最高0.9s

还在鱼C吗？大神，看了你留下的那段判断是否为质数的代码，对你十分钦佩，希望可以有机会讨教{:10_254:}

996982937 发表于 2019-2-24 20:49:49

#include<stdio.h>
#include<math.h>
int prime(long int x);
void main()
{
int i;
long int a;
for(i=1,a=2;i<=10001;a++)
{
if(prime(a))
{
i++;
}
else
{
continue;
}
}
a-=1;
printf("%d\n",a);
}
int prime(long int x)
{
long int a=2;
int flag=1;
for(a=2;a<=(long int)sqrt((double)x);a++)
{
if(x%a==0)
{
flag=0;
break;
}
else
{
continue;
}
}
return flag;
}

//用时0.28s

王小召 发表于 2019-4-10 14:35:16

运行结果：104743
用时：0.34320219999999996

import time
import math

def isprime(num):
num_s = int(math.sqrt(num))
for i in range(2, num_s + 1):
   if num % i == 0:
         return False
         break
return True

def get_next(count):
num = 1
while count:
   num += 1
   if isprime(num):
         count -= 1

return num

print(get_next(10001))
print(time.process_time())

ietar 发表于 2019-4-22 18:47:55

python 这肯定谈不上算法了太莽
104743

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

def p7(num=10001):
count = 0
a=2
while num-count :
   if is_prime(a):
         count += 1
   a += 1
return a-1
p7()

永恒的蓝色梦想 发表于 2019-8-3 10:58:26

本帖最后由永恒的蓝色梦想于 2020-7-31 17:38 编辑

def primes(end, /):
primelist = * (end + 1)
primelist = primelist = False

for index, prime in enumerate(primelist[: end >> 1]):
   if prime:
         for j in range(i << 1, end + 1, i):
            primelist = False

return

print(primes(110000))

1666194196 发表于 2019-10-9 15:28:07

#include <stdio.h>
void main(){
//列出前 6个素数，它们分别是 2、3、5、7、11和13。我们可以看出，第 6个素数是 13。
//第 10,001个素数是多少？
int i,j,flag,count=0;//count来记录有几个素数 ,flag用来记录是否为质数
for(i=2;;i++){
for(j=2;j<i;j++){//2到本身 -1，
if(i%j==0){ //如果能整除说明有因数，不是质数
flag=0;//count不 +1
break;//所以跳出for循环
}else{
flag=1;//否则就是质数，count+1
}
}
if(flag){
count++;//质数计数器 +1
}
flag=0;//清零
if(count==10001){
printf("%d\n",i);//输出这个数
break;//跳出while循环
}
}
}

带上面具的孩纸 发表于 2019-10-23 14:29:54

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

bool Prime(int num);

bool Prime(int num)
{
int i;
int tmpe;

//单独处理
if(num == 2 || num == 3)
{
   return 1;
}
//不在6的倍数两侧的一定不是质数
if(num % 6 != 1 && num % 6 != 5)
{
   return 0;
}
//在6倍数两侧也不一定是质数
tmpe = sqrt(num);

for(i = 5;i <= tmpe;i += 6)
{
   if(num % i == 0 || num % (i+2) == 0)
   {
         return 0;
   }
}
//剩下质数
return 1;
}

int main(void)
{
int count = 0;//计数器
int num = 1;

while(count != 10001)
{
   //num++;
   if(Prime(++num))
   {
      count++;
   }
}
printf("%d\n",num);

return 0;
}

结果 104743
如有错误欢迎指出

foxiangzun 发表于 2019-11-5 18:55:11

代码太丑。。但是运算速度还行，花了大概 10s 的样子

list1 = []
for i in range(2, 101) :
   flag = 0
   for j in range(2, ((i + 1) // 2) + 1) :
            if i % j == 0 :
                     flag += 1
   if flag < 1 :
            list1.append(i)
print(list1)
print(len(list1))
num = list1[-1] + 2
while 1 :
   flag = 0
   for i in list1 :
            if num % i == 0 :
                     flag += 1
                     num += 2
                     break
   if flag == 0 :
            print(num)
            list1.append(num)
   if len(list1) == 10001 :
            break
print(list1[-1])

长大1/2 发表于 2020-1-26 10:26:27

#include <stdio.h>
#include <math.h>
#define NUM 10001
int main(){
   int i;
   int j;
   int count = 0;

   for (i = 2;;i++){
            int flag = 1;
            for (j = 2;j <= sqrt(i);j++){
                     if (i % j == 0){
                           flag = 0;
                           break;
                     }
            }
            if (flag){
                     count++;
                     if (count==NUM){
                           break;
                     }
            }

   }

   printf("%d(%d)\n",i,count);
   return 0;
}

代号-K 发表于 2020-3-11 19:39:33

本帖最后由代号-K 于 2020-3-11 19:50 编辑

答案104743
记得一个有这么一种算法，穷举法，先去除2的倍数，然后是3的倍，然后是5的倍数
算法以空间换时间
#include <QCoreApplication>
int calculate(int flag)
{
int array = {0};
array = 2;
int i = 1;
int j = 3;
int k = 0;
int yes = 1;
while(true)
{
   if(i == flag)
   {
         break;
   }
   else
   {
   k = 0;
         while(k < i)
         {
            if(j % array == 0)
            {
               yes = 0;
   break;
            }
k++;
         }
         if(yes)
         {
            array = j;
         }
   }
   j++;
   yes = 1;
}
return array;
}
int main(int argc, char *argv[])
{
int sum = calculate(10001);
printf("%d\n",sum);
return 0;
}

leon0149 发表于 2020-5-8 21:51:00

本帖最后由 leon0149 于 2020-5-8 21:52 编辑

0.127s104743
#include <stdio.h>
#include <time.h>

#define MAX 10001

int count = 1;
void get_prime(int num, int *prime){
*(prime + count) = num;
count++;
}

int isPrime(int num,int *prime){
int ret = 0;
for (int i = 0; i < count ;++i) {
   if (num % *(prime + i) == 0){
         return ret;
   }
}
get_prime(num, prime);
ret = 1;

return ret;
}

int main(void)
{
clock_t start, finish;
double duration;
start = clock();
int prime;
prime = 2;
int i = 3;
while (count != 10001){
   isPrime(i, prime);
   i += 2;
}
finish = clock();
for (int j = 0; j < count; ++j) {
   printf("%d:%d\n", j + 1 , prime);
}
duration = (double)(finish - start)/CLOCKS_PER_SEC;
printf("%.3f", duration);

return 0;
}

SYSTEM0 发表于 2020-5-21 11:34:31

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

可以试到sqrt(n)就行了

数据小随从 发表于 2020-6-11 13:51:34

#include<stdio.h>
#include<stdlib.h>

long isprime(long num)//判断是否为质数
{
long j;
for (j = 2; j < num; j++)
{
if (num%j == 0)
break;
}
if (j >= num)
return 1;
}

void main()
{
long n = 0;//用于统计质数的个数
long i;
for (i = 2;; i++)
{
if (isprime(i) == 1)
{
n++;
if (n == 10001)
{
printf("第10001个质数=%ld\n", i);//输出第10001个质数
break;
}
}
}
system("pause");
}
输出结果为:第10001个质数=104743

永恒的蓝色梦想 发表于 2020-6-27 19:49:38

cupbbboom 发表于 2018-11-23 15:11
还在鱼C吗？大神，看了你留下的那段判断是否为质数的代码，对你十分钦佩，希望可以有机会讨教{:10_254 ...

这是最基础的判断质数方法了……

页: 1 2 3 [4] 5

鱼C论坛's Archiver