参考文章:点击打开链接
对于判断素数大概有两类方法1:试除法2:筛选法
还有一个米勒-拉宾检验方法此处不再展开。
试除法:不断地尝试能否整除。比如要判断自然数 x 是否质数，就不断尝试小于 x 且大于1的自然数，只要有一个能整除，则 x 是合数；否则，x 是质数。
筛选法:首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数……上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。 筛选法如图所示
具体代码如下:
/** 判断素数最优的方法 */ bool isPrimeOptimize(int n){ int i = 2; //这里的(n / i）是从筛选法中获取的比例值 // i/j 米勒/拉宾检验 for (; i <= (n / i); i++) { if (n % i == 0) { break; } } if (i > (n / i)) { //NSLog(@"此数是素数 %d", n); return true; } return false; } /** 判断素数开根号方法 */ bool isPrimeSqrt(int n){ int i = 2; int sqrtN = sqrt(n); for (; i <= sqrt(n); i++) { if (n % i == 0) { break; } } if (i > sqrtN) { //NSLog(@"此数是素数 %d", n); return true; } return false; } #define kDefault (-1) #define kDefaultNot (0) #define kDefaultYes (1) bool isTestSelecting(int n){ #if 0 - 测试 for (int i = 2; i <= 100; i++) { bool is = isPrime(i); if (is) { printf("this is prime %d\n", i); } } return false; #endif #if 1 - 筛选法每位按int数据来处理 int length = n + 1;//从0开始 int arr[length]; memset(arr, kDefault, sizeof(int) * length); for (int i = 0; i <= n; i++) { printf("the arr[%d] is %d\n", i, arr[i]); } arr[1] = kDefaultYes; for (int i = 2; i <= n; i++) { bool isPrimeBool = false; if (arr[i] == kDefaultNot) { isPrimeBool = false; }else{ isPrimeBool = isPrimeOptimize(i); arr[i] = kDefaultYes; } if (isPrimeBool) { for (int j = i; j <= n / i; j++) { //i*j = n; int position = i * j; arr[position] = kDefaultNot;//kDefaultValue is No } } } for (int i = 1; i <= n; i++) { //printf("the arr[%d] is %d\n", i, arr[i]); if (arr[i] == kDefaultYes) { printf("the value is %d\n", i); } } return false; #endif } void print_int_8bit(char value){ unsigned char index = 0x80; while(index > 0){ putchar(value & index ? '1' : '0'); index >>= 1; } printf("\n"); } void setPositionBit(char *pointer, int position, int v){ char value = pointer[position / 8]; print_int_8bit(value); if (v == 0) { value = (~(0x01 << (position % 8))) & value; pointer[position / 8] = value; print_int_8bit(value); }else if (v == 1){ value = (0x01 << (position % 8)) | value; pointer[position / 8] = value; print_int_8bit(value); } } bool getbitValue(char *pointer, int position){ return pointer[position / 8] >> (position % 8) & 0x01; } /** 判断素数筛选法每位按照位来处理 */ void testIsPrimeSelecting(int n){ int length = n + 1;//从0开始 int align8 = align8Bit(length); char * pointer = (char *)calloc(align8, sizeof(char)); //默认都是 memset(pointer, 0xff, sizeof(char) * align8); //从0开始第一位设为1 for (int i = 0; i <= n; i++) { printf("the pointer[%d] is %d\n", i, pointer[i / 8] >> (i % 8) & 0x01); } for (int i = 0; i <= n; i++) { printf("the pointer[%d] is %d\n", i, pointer[i / 8] >> (i % 8) & 0x01); } for (int i = 2; i <= n; i++) { bool isPrimeBool = false; if (getbitValue(pointer, i) == false) { isPrimeBool = false; }else{ isPrimeBool = isPrimeOptimize(i); if (isPrimeBool == false) { setPositionBit(pointer, i, kDefaultNot); } } if (isPrimeBool) { for (int j = i; j <= n / i; j++) { int position = i * j; setPositionBit(pointer, position, kDefaultNot); } } } for (int i = 1; i <= n; i++) { if (getbitValue(pointer, i) == true) { printf("the value 是素数 is %d\n", i); } } } unsigned int align8Bit(unsigned int n){ return calc_alignFounction2(n, 8); } unsigned int calc_alignFounction1(unsigned int n,unsigned align){ if (n / align * align == n) { return n; } return (n / align + 1) * align; } /* 例如8字节对齐要求，后三位为0. (align-1)表示后三位111. size+(aling-1)会导致进位。 &～（aling-1）去除后面多余的。 */ unsigned int calc_alignFounction2(unsigned int n, unsigned align){ return (n + (align - 1)) & (~(align - 1)); }