今天跟随周老师学到了一个新的求素数的方法，按照老师的编程方法，比较简单的就求得了素数，以下代码中，有一个方法是自己写的，一个是按照老师的思路来的：
#include "stdafx.h" #include <math.h> #define nRange 40000 //找出40000以内的素数（筛法）4203 void findPrimeNumber(int *arr, int nLen) { if (arr == NULL) { return; } int i = 2; int temp = 1; int index = 0; for (index = 1; index <= nLen; index++) { arr[index] = 1; } for (i = 2; i <= nLen; i++) { int k = sqrt(i); int j = 2; if (arr[i] == 0) { continue; } for (; j <= k; j++) { if (i%j == 0) { arr[i] = 0; break; } } if (j > k) { arr[i] = 1; int m = pow(i, 2); for (; m <= nLen; m++) { if (arr[m] == 0) { continue; } if (m%i == 0) { arr[m] = 0; } } } } while (temp <= nLen) { if (arr[temp] == 1) { printf("%d ", temp); } temp++; } temp--; } //比较正确的解法：筛选法 void find_prime(int* arr, int n) { if (n < 1 || arr == NULL) { return; } int i = 0; int j = 1; for (i = 0; i < nRange; i++) { arr[i] = 1; } for (i = 2; i < nRange; i++) { if (arr[i] == 1) { for (j = 2; i*j < nRange; j++) { arr[i*j] = 0; } } } for (i = 1; i < nRange; i++) { if (arr[i] == 1) { printf("%d ", i); } } } int main() { int arr[nRange] = { 0 }; //findPrimeNumber(arr, nRange); find_prime(arr, nRange); return 0; }
