题目7：找出第10001个质数

zzzgod

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

塔利班

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

笨方法

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

山有扶苏啊

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

山有扶苏啊

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[10000]

cupbbboom

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

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

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

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

996982937

#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

王小召

运行结果：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

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()
        

永恒的蓝色梦想

def primes(end, /):
    primelist = [True] * (end + 1)
    primelist[0] = primelist[1] = False

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

  return [i for i, prime in enumerate(primelist) if prime]


print(primes(110000)[10001-1])

1666194196

#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循环
                }
        }
}

带上面具的孩纸

#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

代码太丑。。但是运算速度还行，花了大概 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

#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

答案  104743
记得一个有这么一种算法，穷举法，先去除2的倍数，然后是3的倍，然后是5的倍数
算法以空间换时间

#include <QCoreApplication>
int calculate(int flag)
{
    int array[flag] = {0};
    array[0] = 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[k] == 0)
                {
                    yes = 0;
                    break;
                }
                k++;
            }
            if(yes)
            {
                array[i++] = j;
            }
        }
        j++;
        yes = 1;
    }
    return array[flag-1];
}
int main(int argc, char *argv[])
{
    int sum = calculate(10001);
    printf("%d\n",sum);
    return 0;
}

leon0149

0.127s  104743

#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[MAX];
    prime[0] = 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[j]);
    }
    duration = (double)(finish - start)/CLOCKS_PER_SEC;
    printf("%.3f", duration);

    return 0;
}

SYSTEM0

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

可以试到sqrt(n)就行了

数据小随从

#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

永恒的蓝色梦想

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

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