题目7：找出第10001个质数

Eagle.Tong

#求解第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

天之南

#include<stdio.h>

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

铭记太阳

答案是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;
}

格式化、

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

运维小书童

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+、 学习下其他鱼友的思路看看 我的脑浆先这样了。。。。

运维小书童

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

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

运维小书童

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

麦特的灰

#找出第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

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

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

答案 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;
}

幻世伽蓝

#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

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

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

刘亮

//运行时间四秒之内
//题目:找出第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)
                          ;
                    else  break;
                }
             if(    j==i   )
                temp++  ;   //此时temp加一的值为10001所以此时J为所求的质数
                j++;       //最后结果多算了一次，所以输出时结果要减一。
          }
           printf("%d是第10001个质数",j-1);
            return  0;
}

刘亮

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

答案也是：104743

ufo20085

#找出第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[x-1]
        i+=1    
    
            
def main():
    starttime = time.time()
    print(getlist(10001))
    endtime = time.time()
    print(endtime-starttime)
if __name__=="__main__":
    main()

python，用时0.2秒，104743

晓丘

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秒左右

晓丘

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

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