Project_Euler-07 题解

题目

思路

一个线性筛解决问题，当然也可以用埃式筛或者标准的暴力破解，这里选用最优秀的方式，顺便复习一下线性筛的内容：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<time.h>// 返回一个指向存放n个数之前所有素数的数组
int *__PrimeGet(int n) {// arr以下标为数字，作为标记数组，0表示质数，1表示合数int *arr = (int *)malloc(sizeof(int) * n);// prime存放已经被筛出来的素数int *prime = (int *)malloc(sizeof(int) * n);// 全部初始化为0memset(arr, 0, sizeof(int) * n);memset(prime, 0, sizeof(int) * n);// pos表示prime中最后一个素数后一个地址，从1开始存放int pos = 1;//遍历arr中所有元素，都判断一遍，i表示正在判断的数for (int i = 2; i <= n; i++) {// 如果为素数，存放到prime数组中。if (!arr[i]) prime[pos++] = i;// 遍历已经筛出的素数for (int j = 1; j < pos; j++) {// 如果当前判断值i与当前遍历到的素数乘积大于要求范围n，停止判断if (i * prime[j] > n) break;// 将当前遍历到的素数的i倍的数标记为1arr[i * prime[j]] = 1;// 当前判断值是第一个可以除掉j值对应素数的，说明prime[j]是该数的最小质因数if (i % prime[j] == 0) break;}}free(arr);return prime;
}// 这个程序是用来输出n之前所有素数的程序，如果你想要知道第10001个质数是多少，
// 你可以将结果重定向到一个带行号的文本文件中，查看第10001行的值，就是答案。
int main(){int n;scanf("%d", &n);int *prime = __PrimeGet(n);for (int i = 1; prime[i]; i++) printf("%d\n", prime[i]);free(prime);return 0;
}
```