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

Eagle.Tong 发表于 2017-4-17 01:36:11

#求解第10001个素数

import math
import time

start = time.time()

def ifprime(n):
   r = int(math.sqrt(n))
   for i in range(2,r+1):
         if n%i == 0:
            return 0
   return 1

count = 0
number = 2
while True:
if ifprime(number):
   count += 1
if count == 10001:
   print(number)
   break
number += 1

end = time.time()
print(end-start)

结果：104743
时间：0.5383784770965576

天之南 发表于 2017-4-30 22:31:49

本帖最后由天之南于 2017-4-30 22:34 编辑

#include<stdio.h>

int main()
{
const int L = 10001;
int arr = { 2 };
int i = 1;
for (int x = 3;i < L;x+=2)
{
int j = 0;
while (j < i && x % arr != 0 && ++j);
if (i == j) {
arr = x;
i++;
}
}
printf("%d\n", arr);
}

铭记太阳 发表于 2017-5-4 17:07:36

答案是104743

#include<stdio.h>

int main(void)
{
int i=14,j,num=6;

while(1)
{
if(i%2==0) goto Next_Num;
for(j=3; j<=i/2 ;j+=2) //这样可以减少大量冗余计算
{
if(i%j==0) goto Next_Num;
}
num++;
if(num==10001) break;
Next_Num:
++i;
}
printf("第%d个素数是 %d\n",num,i);
return 0;
}

格式化、 发表于 2017-6-7 16:09:44

public static void main(String[] args) {
// 7、前六个质数是2,3,5,7,11,13其中第6个是13.
// 第10001个质数是多少?
int i=1,j=3;
while(i!=10001){
while(true){
if(cmp(j++)){
break;
}
}
i++;
}
System.out.println(j-1);

}
public static boolean cmp(int num){
for(int i=2;i<num;i++){
if(num%i==0){
return false;
}
}
return true;
}

运维小书童 发表于 2017-8-4 17:31:18

import time

def FindPrime(count):
'''获得第N个质数
---由3开始累加2判断是否质数初始化质数个数1
---每出现一个质数个数prime_count+1

'''
prime_count = 1
number = 3
while 1:
   flag = 0
   r = (number + 1) // 2
   for i in range(2,r+1):
         if number%i == 0:
            flag = 1
            break
   if flag == 0:
         prime_count += 1
   if prime_count == count:
         break
   number += 2
print(number)

start = time.clock()
FindPrime(10001)
end = time.clock()
print('耗时%f s'%(end - start))

运行16s+、学习下其他鱼友的思路看看我的脑浆先这样了。。。。

运维小书童 发表于 2017-8-4 17:47:22

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

{:5_98:}为什么判断是否质数 n%ii范围<n的平方根啊啊啊啊啊啊
- -速度就差这边了。

运维小书童 发表于 2017-8-4 17:50:39

#r = (number + 1) // 2运行速度 17.56s
r = int(number ** 0.5) 运行速度 0.201s
{:5_99:}

麦特的灰 发表于 2017-9-2 10:24:09

#找出第10001个质数是多少
k=1
num=2
i=0
pd=1
while (k<10002):
if (num==2 or num==3):
   #print (num,k)
   k=k+1
else:
   for i in range(2,(num+1)//2):
         if (num%i==0):
            pd=0
            break
   if (i ==(num+1)//2-1 and num!=6):
         #print (num,k)
         k=k+1
num=num+1
print (num-1,k)

BngThea 发表于 2017-9-11 17:27:47

def check(n):
for i in range(2,n//2+1):
   if not (n%i):
         return False
return True

result = 2
count = 1
while count < 10002:
if check(result):
   count += 1
result += 1

print(result-1)

jerryxjr1220 发表于 2017-9-29 17:19:37

AArdio编译：
import console;
import time.timer

console.setTitle("test");

time.timer.start();

var is_prime = function(n){
if n%2==0 {
return false
}
for i=3;n**0.5;2 {
if n%i==0 {
return false
}
}
return true
}

var tab = {2;}
p = 3
while #tab<10001 {
if is_prime(p) {
table.push(tab,p)
}
p += 2
}
console.print(table.pop(tab));

console.print(time.timer.endTick(), '毫秒');
console.pause();
console.close()
104743
70.252956390381 毫秒
请按任意键继续 ...

zjhnz 发表于 2018-1-4 16:25:43

答案 104743
#include <stdio.h>
#include <math.h>

int isprem( int n)
{
int i;
for(i=2; i<=sqrt(n); i++)
{
if (n%i==0)
{
return 0;
}
}

return 1;
}

int main(void)
{
int count=0;
int n=2;

while (count!=10001)
{
if(isprem(n))
{
count++;
}
n++;
}

printf("%d",--n);

return 0;
}

幻世伽蓝 发表于 2018-1-10 17:24:08

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

int isPrimer(int n)
{
int i;
for(i=2;i<=sqrt(n);i++){
   if(n % i == 0){
         return 0;
   }
}
return 1;
}

int main()
{
int n = 2,s=0;

for(;;n++){
   if(isPrimer(n)){
         s++;
   }
   if(s==10001){
         break;
   }
}
printf("%d\n",n);
return 0;
}

阿bang 发表于 2018-3-27 14:30:22

def isPrime(num):
if num == 2:
   return True
elif num < 2 or num % 2 == 0:
   return False
else:
   for i in range(3, int(num ** 0.5) + 1, 2):
         if num % i == 0:
            return False
   else:
         return True

num = 1
count = 0
while True:
if isPrime(num):
   count += 1
if count == 10001:
   print num
   break
num += 1

refracted_ray 发表于 2018-4-14 20:48:50

import math
# 判断n是否质数
def prime(n):
flag=True # flag=True表示n是质数，False表示n是合数
# 当n=2时本应分开讨论，但因为flag一开始就是True，所以不影响结果
for i in range(2,int(math.sqrt(n))+1):
# 任意一个数能整除n，则n是合数
if n%i==0:
flag=False
break
if flag:
return True # n是质数则返回True
else:
return False # n是合数则返回False

i=1 # i表示质数的序列编号。第1个质数是2，从第2个质数3开始计数，因此i初始值设为1
n=1
while i<10001:
n+=2 # 排除所有偶数
# 若n是质数，则质数序列编号i+1
if prime(n):
i+=1

print ('第10001个质数是：%d'%n)
结果是104743

刘亮发表于 2018-4-26 00:19:01

//运行时间四秒之内
//题目:找出第10001个质数
#include<stdio.h>
#include<stdlib.h>
int main()
{
int i; //循环计数变量
int j; //质数变量
int temp; //质数个数变量
for (temp=0;temp<10001; )
   {
      for (i=2;i<j;i++)
         {
               if(j%i !=0)
                     ;
               elsebreak;
            }
         if( j==i )
            temp++; //此时temp加一的值为10001所以此时J为所求的质数
            j++;    //最后结果多算了一次，所以输出时结果要减一。
      }
      printf("%d是第10001个质数",j-1);
         return0;
}

刘亮发表于 2018-4-26 00:22:49

刘亮发表于 2018-4-26 00:19

答案也是：104743

ufo20085 发表于 2018-5-6 17:05:59

#找出第10001个质数
import time
import math

def iszs(x):
k=1
if x == 2:
   return True
else:
   if 2<x<10:
         for i in range(2,x):
            b= x%i
            if b == 0:
               return False
            else:
               continue
         return True
   else:
         a = int(math.sqrt(x))+1
         for i in range(2,a):
            b = x%i
            if b == 0:
               return False
            else:
               continue
         return True
def getlist(x):
i = 2
list_zs=[]
while 1:
   if iszs(i) == True:
         list_zs.append(i)
         #print(list_zs)
         if len(list_zs) == x:
            return list_zs
   i+=1


def main():
starttime = time.time()
print(getlist(10001))
endtime = time.time()
print(endtime-starttime)
if __name__=="__main__":
main()

python，用时0.2秒，104743

晓丘发表于 2018-5-14 17:12:08

import math
def judgePrimes(num):             #素数的判断方法
if num % 2 == 0:
   return False
for i in range(3, int(math.sqrt(num))+1, 2):
   if not num % i:
         return False
else:
   return True

def the10001Primes():
i, j = 3, 1
while j<10001:
   if judgePrimes(i):
         j +=1
   i +=2
i -=2
print('第1001个素数是:%d' % i)

the10001Primes()

答案：104743 运行时间3秒左右

晓丘发表于 2018-5-14 17:21:54

import math
def judgePrimes(num):             #素数的判断方法
if num % 2 == 0:
   return False
for i in range(3, int(math.sqrt(num))+1, 2):
   if not num % i:
         return False
else:
   return True

def the10001Primes():
i, j = 3, 1
while j<10001:
   if judgePrimes(i):
         j +=1
   i +=2
i -=2
print('第1001个素数是:%d' % i)

import time
start = time.clock()
the10001Primes()
end = time.clock()
print(end-start)

答案： 104743运行时间0.6秒左右

li1347zhen 发表于 2018-5-22 19:26:24

#include<stdio.h>
#include<math.h>
long int prime(long int x);
long int nextprime(long int x);
int main()
{
int i=1;
int primenumber=2;
while(i<10001){
   primenumber=nextprime(primenumber);
   printf("nextprime=%d\n",primenumber);
   i++;
}
printf("%d\n",primenumber);
}
long int prime(long int x)
{
long int i=2;
long int y;
y=sqrt(x);
if(x==1)
   return 0;
for(i=2;i<=y;i++){
   if(x%i==0){
         return 0;
   }
}
return 1;
}
long int nextprime(long int x)
{
x+=1;
while(1){
   if(prime(x)){
         return x;
   }
   x++;
}
}

页: 1 2 [3] 4 5

鱼C论坛's Archiver