半质数的个数

发布时间:2016-12-10 13:02:26 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"半质数的个数",主要涉及到半质数的个数方面的内容,对于半质数的个数感兴趣的同学可以参考一下。

#include <iostream> #include <time.h> #include <windows.h> using namespace std; int Prime(int x,int y) { if(x <2 || y < 2) return 0; int nCount = 0; for(int n=x; n<=y; ++n) { for(int i=2; i<n; ++i) { int tmp1 = n/i; if(tmp1 < i) break; if(tmp1 * i == n) //如果能整出 { int j = 2; for(j; j<tmp1; ++j) { if((tmp1%j==0) || (j<i && i%j ==0)) { break; } } if(j>=tmp1) { ++nCount; } break; } } } return nCount; } int main() { int nMin = 2,nMax = 20000; printf("%d到%d的半质数:\n",nMin,nMax); int nStar = GetTickCount(); cout<<Prime(nMin,nMax)<<endl; int nEnd = GetTickCount(); cout<<"time = "<<nEnd-nStar<<endl; system("pause"); return 0; }   #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <Windows.h> using namespace std; int getNum(int x, int y) { if(x < 1 || x > y) return 0; bool * bPrime = (bool *)malloc(y * sizeof(bool)); bPrime[0] = false; // 2 bPrime[1] = false; // 3 for(int i = 2; i < y; i++) // {false,false true,true......} { bPrime[i] = true; } for(int i = 2; i < y; i ++) { if(bPrime[i]) { if(y/i < i) { break; } for(int j = i * i; j < y; j += i) // 合数 { bPrime[j] = false; } } } int nPrime = 0; for(int i = 2; i < y; i++) { if(bPrime[i]) nPrime++; //统计还剩余多少个质数 } int * Prime = (int *)malloc(nPrime * sizeof(int)); for(int i = 2, j = 0; i < y; i++) { if(bPrime[i]) { Prime[j++] = i; //得到质数 } } int nHalfPrime = 0; for(int i = 0; i < nPrime; i++) { if(y / Prime[i] < Prime[i]) //排除较大 * 较小的情况 { break; } for(int j = i; j < nPrime; j++) { if(j != i && y / Prime[i] < Prime[j]) { break; } int HalfPrime = Prime[i] * Prime[j]; if(HalfPrime >= x) { nHalfPrime++; } } } free(Prime); free(bPrime); return nHalfPrime; } int main() { int nStat = GetTickCount(); printf("%d\n",getNum(2, 2000000)); printf("%d\n",GetTickCount()-nStat); system("pause"); }

上一篇:sql_表的约束1
下一篇:网络编程之路---4

相关文章

关键词: 半质数的个数

相关评论