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

塔利班

1. def prime():
   
2.     yield 2
   
3.     x=3
   
4.     while True:
   
5.         a=True
   
6.         for i in range(3,int(x**0.5)+1,2):
   
7.            if x%i==0:
   
8.                a=False
   
9.                break
   
10.         if a:
    
11.             yield x
    
12.         x+=2
    
13. a=prime()
    
14. for i in range(10001):
    
15.     p=next(a)
    
16. 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);
}

山有扶苏啊

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

山有扶苏啊

1. from math import sqrt
   
2. 
   
3. def is_prime(n):
   
4.     if n == 1:
   
5.         return False
   
6.     for i in range(2, int(sqrt(n)) + 1):
   
7.         if n % i == 0:
   
8.             return False
   
9.     return True
   
10. 
    
11. result = []
    
12. for t in range(1, 10000000):
    
13.     if is_prime(t):
    
14.         result.append(t)
    
15. print(result[10000]

复制代码

cupbbboom

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

1. import time
   
2. 
   
3. 判断质数
   
4. def isfrime(x): # 默认传入参数为大于1的整数，不判断了
   
5.         t = True
   
6.         # if x % 2 == 0 or x % 3 == 0 or x % 5 ==0 or x % 7 == 0:
   
7.         #                 t = False
   
8.         for i in range(2,x):
   
9.                 if x % i == 0:
   
10.                         t = False
    
11.                         break
    
12.         return t
    
13. 
    
14. n = 8
    
15. count = 4
    
16. print('计算开始')
    
17. start_time = time.time()
    
18. while count < 10001:
    
19.         if isfrime(n) == True:
    
20.                 count += 1  
    
21.         n += 1
    
22. result = n - 1     # 这是结果;减去当count=10001时，后面还增加的1
    
23. print('结果为：%s'%str(result))
    
24. end_time = time.time()
    
25. print('耗时：%s 秒'%str(end_time - start_time))       

复制代码

这是大神的：

1. def is_prime(n):
   
2.     if n == 2:
   
3.         return True
   
4.     elif n % 2 == 0:
   
5.         return False
   
6.     i = 3
   
7.     while i <= n**0.5:
   
8.         if n % i == 0:
   
9.             return False
   
10.         i += 2
    
11.     return True
    
12. 
    
13. 
    
14. def getnth(n):
    
15.     if n == 1:
    
16.         return 2
    
17.     elif n == 2:
    
18.         return 3
    
19.     prime = 3
    
20.     x = 2
    
21.     while x < n:
    
22.         prime += 2
    
23.         if is_prime(prime):
    
24.             x += 1
    
25.     return prime
    
26. 
    
27. import time
    
28. start_time = time.time()
    
29. print(getnth(10001))
    
30. end_time = time.time()
    
31. 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

1. import time
   
2. import math
   
3. 
   
4. 
   
5. def isprime(num):
   
6.     num_s = int(math.sqrt(num))
   
7.     for i in range(2, num_s + 1):
   
8.         if num % i == 0:
   
9.             return False
   
10.             break
    
11.     return True
    
12. 
    
13. 
    
14. def get_next(count):
    
15.     num = 1
    
16.     while count:
    
17.         num += 1
    
18.         if isprime(num):
    
19.             count -= 1
    
20. 
    
21.     return num
    
22. 
    
23. print(get_next(10001))
    
24. print(time.process_time())

复制代码

ietar

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

1. def is_prime(a):
   
2.     for i in range(2,int(sqrt(a)+1)):
   
3.         if not a%i:
   
4.             return False
   
5.     return True
   
6.    
   
7. def p7(num=10001):
   
8.     count = 0
   
9.     a=2
   
10.     while num-count :
    
11.         if is_prime(a):
    
12.             count += 1
    
13.         a += 1
    
14.     return a-1
    
15. p7()
    
16.         

复制代码

永恒的蓝色梦想

1. def primes(end, /):
   
2.     primelist = [True] * (end + 1)
   
3.     primelist[0] = primelist[1] = False
   
4. 
   
5.     for index, prime in enumerate(primelist[: end >> 1]):
   
6.         if prime:
   
7.             for j in range(i << 1, end + 1, i):
   
8.                 primelist[j] = False
   
9. 
   
10.   return [i for i, prime in enumerate(primelist) if prime]
    
11. 
    
12. 
    
13. 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循环
                }
        }
}

带上面具的孩纸

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <math.h>
   
4. #include <stdbool.h>
   
5. 
   
6. bool Prime(int num);
   
7. 
   
8. bool Prime(int num)
   
9. {
   
10.     int i;
    
11.     int tmpe;
    
12. 
    
13.     //单独处理
    
14.     if(num == 2 || num == 3)
    
15.     {
    
16.         return 1;
    
17.     }
    
18.     //不在6的倍数两侧的一定不是质数
    
19.     if(num % 6 != 1 && num % 6 != 5)
    
20.     {
    
21.         return 0;
    
22.     }
    
23.     //在6倍数两侧也不一定是质数
    
24.     tmpe = sqrt(num);
    
25. 
    
26.     for(i = 5;i <= tmpe;i += 6)
    
27.     {
    
28.         if(num % i == 0 || num % (i+2) == 0)
    
29.         {
    
30.             return 0;
    
31.         }
    
32.     }
    
33.     //剩下质数
    
34.     return 1;
    
35. }
    
36. 
    
37. int main(void)
    
38. {
    
39.     int count = 0;//计数器
    
40.     int num = 1;
    
41. 
    
42.     while(count != 10001)
    
43.     {
    
44.        //num++;
    
45.        if(Prime(++num))
    
46.        {
    
47.            count++;
    
48.        }
    
49.     }
    
50.     printf("%d\n",num);
    
51. 
    
52.     return 0;
    
53. }

复制代码

结果 104743
如有错误欢迎指出

foxiangzun

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

1. list1 = []
   
2. for i in range(2, 101) :
   
3.         flag = 0
   
4.         for j in range(2, ((i + 1) // 2) + 1) :
   
5.                 if i % j == 0 :
   
6.                         flag += 1
   
7.         if flag < 1 :
   
8.                 list1.append(i)
   
9. print(list1)
   
10. print(len(list1))
    
11. num = list1[-1] + 2
    
12. while 1 :
    
13.         flag = 0
    
14.         for i in list1 :
    
15.                 if num % i == 0 :
    
16.                         flag += 1
    
17.                         num += 2
    
18.                         break
    
19.         if flag == 0 :
    
20.                 print(num)
    
21.                 list1.append(num)
    
22.         if len(list1) == 10001 :
    
23.                 break
    
24. 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的倍数
算法以空间换时间

1. #include <QCoreApplication>
   
2. int calculate(int flag)
   
3. {
   
4.     int array[flag] = {0};
   
5.     array[0] = 2;
   
6.     int i = 1;
   
7.     int j = 3;
   
8.     int k = 0;
   
9.     int yes = 1;
   
10.     while(true)
    
11.     {
    
12.         if(i == flag)
    
13.         {
    
14.             break;
    
15.         }
    
16.         else
    
17.         {
    
18.             k = 0;
    
19.             while(k < i)
    
20.             {
    
21.                 if(j % array[k] == 0)
    
22.                 {
    
23.                     yes = 0;
    
24.                     break;
    
25.                 }
    
26.                 k++;
    
27.             }
    
28.             if(yes)
    
29.             {
    
30.                 array[i++] = j;
    
31.             }
    
32.         }
    
33.         j++;
    
34.         yes = 1;
    
35.     }
    
36.     return array[flag-1];
    
37. }
    
38. int main(int argc, char *argv[])
    
39. {
    
40.     int sum = calculate(10001);
    
41.     printf("%d\n",sum);
    
42.     return 0;
    
43. }
    

复制代码

leon0149

0.127s  104743

1. #include <stdio.h>
   
2. #include <time.h>
   
3. 
   
4. #define MAX 10001
   
5. 
   
6. int count = 1;
   
7. void get_prime(int num, int *prime){
   
8.     *(prime + count) = num;
   
9.     count++;
   
10. }
    
11. 
    
12. int isPrime(int num,int *prime){
    
13.     int ret = 0;
    
14.     for (int i = 0; i < count ;++i) {
    
15.         if (num % *(prime + i) == 0){
    
16.             return ret;
    
17.         }
    
18.     }
    
19.     get_prime(num, prime);
    
20.     ret = 1;
    
21. 
    
22.     return ret;
    
23. }
    
24. 
    
25. 
    
26. int main(void)
    
27. {
    
28.     clock_t start, finish;
    
29.     double duration;
    
30.     start = clock();
    
31.     int prime[MAX];
    
32.     prime[0] = 2;
    
33.     int i = 3;
    
34.     while (count != 10001){
    
35.         isPrime(i, prime);
    
36.         i += 2;
    
37.     }
    
38.     finish = clock();
    
39.     for (int j = 0; j < count; ++j) {
    
40.         printf("%d:%d\n", j + 1 , prime[j]);
    
41.     }
    
42.     duration = (double)(finish - start)/CLOCKS_PER_SEC;
    
43.     printf("%.3f", duration);
    
44. 
    
45.     return 0;
    
46. }

复制代码

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 ...

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