贵州企业网站建设案例,wordpress 登录 缓存,在线制作网站地图,可以做100张照片的软件一、检查n是否为素数 最简单思路#xff1a;所有可能的因数全部试一遍。 int gg(int n)
{for(int i2;in;i){if((n%i)0)return 0;//有因数就不是素数咯}return 1;
} 进一步思考#xff1a;没必要枚举所有的数#xff0c;每一个小于n^(1/2)的因数i#xff0c;一定有一个大…一、检查n是否为素数 最简单思路所有可能的因数全部试一遍。 int gg(int n)
{for(int i2;in;i){if((n%i)0)return 0;//有因数就不是素数咯}return 1;
} 进一步思考没必要枚举所有的数每一个小于n^(1/2)的因数i一定有一个大于n^(1/2)的因数j与之对应也就是i*jn所以枚举小于等于n^(1/2)的因数即可 int gg(int n)
{for(int i2;i*in;i){if((n%i)0)return 0;}return 1;
} 二、约数枚举 上面已经说过不需要枚举所有因数枚举出某小因数以后算出对应的大因数即可。
vectorint gg(int n)
{vectorint a;for(int i2;i*in;i){if((n%i)0){a.push_back(i);if((n/i)!i)a.push_back(n/i);//根号n的情况不要重复添加}}return a;
} 三、埃氏筛法 只对一个整数操作O(N)已经足够了如果对许多整数进行素性检测还有更高效的算法比如埃氏筛法。
问题枚举n以内所有素数
操作先把所有整数列出来然后把2的倍数全部剔除然后是三的以此类推遍历所有素数把倍数全部划去。
对于每个数字i如果没被划去他一定是素数因为他不是任何2到i-1数字的倍数。然后就开始划它的倍数就好。
int a[maxx];
int b[maxx1];
int gg(int n)
{int p0;//记录素数个数for(int i0;in1;i)b[i]1;b[0]0;b[1]0;//准备完毕for(int i2;in;i){if(b[i]){a[p]i;//记录素数和个数for(int j2*i;jn;ji)b[j]0;//剔除倍数}}return p;//返回素数个数
}
四、区间筛法 给定整数a和b请问区间[a,b)内有多少个素数
思路之前说过因为b以内合数的最小质因数一定不超过sqrt(b),如果有sqrt(b)以内的素数表的话就可以把筛选法用在[a,b)上了,先分别做好[2,sqrt(b))的表和[a,b)的表然后从[2,sqrt(b))的表中筛得素数的同时也将其倍数从[a,b)的表中划去最后剩下的就是区间[a,b)内的素数了。
//不gg了这次就来个标准一点的吧
typedef long long ll;
bool is_prime[maxn];
bool is_prime_small[maxn];
void segment_sieve(ll a,ll b)
{for(ll i0;i*ib;i) is_prime_small[i]true; //初始化for(ll i0;ib-a;i) is_prime[i]true; //初始化注意下标变化为了省空间for(ll i2;i*ib;i) {if(is_prime_small[i]) {for(ll j2*i;j*jb;ji) is_prime_small[j]false; //筛选[2,sqrt(b));//(ai-1)/i得到最接近a的i的倍数最低是i的2倍然后筛选for(ll jmax(2LL,(ai-1)/i)*i;jb;ji) is_prime[j-a]false;}}
}
五、线性实现
筛法很多数被处理了不止1遍比如6在素数为2的时候处理1次为3时候又处理一次因此又造成了不必要处理。O(nloglogn)已经基本可以满足一般需要了。
本代码保证每个合数只会被它的最小质因数筛去因此每个数只会被标记一次所以时间复杂度是O(n)
证明略
话不多说上板子
#includecstdio
#includecstring
#define MAXN 100005
#define MAXL 1299710
int prime[MAXN];
int check[MAXL];
int tot 0;
memset(check, 0, sizeof(check));
for (int i 2; i MAXL; i)
{if(!check[i])prime[tot] i;for (int j 0; j tot; j)//****************************************{if (i * prime[j] MAXL)break;//*******************check[i*prime[j]] 1;if (i % prime[j] 0)break;//******}
}
素数基本就这些内容咯。。。。
