网页设计图模板,seo网站内容,设计电子商务网站,android源码下载网站数论#x1f388; 筛质数
最普通的筛法O(nlogn)#xff1a;
void get_primes2(){for(int i2;in;i){if(!st[i]) primes[cnt]i;//把素数存起来for(int ji;jn;ji){//不管是合数还是质数#xff0c;都用来筛掉后面它的倍数st[j]true;}}
}
诶氏筛法 O(nloglogn)#… 数论 筛质数
最普通的筛法O(nlogn)
void get_primes2(){for(int i2;in;i){if(!st[i]) primes[cnt]i;//把素数存起来for(int ji;jn;ji){//不管是合数还是质数都用来筛掉后面它的倍数st[j]true;}}
}
诶氏筛法 O(nloglogn)
void get_primes1(){for(int i2;in;i){if(!st[i]){primes[cnt]i;for(int ji;jn;ji) st[j]true;//可以用质数就把所有的合数都筛掉}}
}
线性筛O(n)
void get_primes(){//外层从2~n迭代因为这毕竟算的是1~n中质数的个数而不是某个数是不是质数的判定for(int i2;in;i){if(!st[i]) primes[cnt]i;for(int j0;primes[j]n/i;j){//primes[j]n/i:变形一下得到——primes[j]*in,把大于n的合数都筛了就//没啥意义了st[primes[j]*i]true;//用最小质因子去筛合数//1)当i%primes[j]!0时,说明此时遍历到的primes[j]不是i的质因子那么只可能是此时的primes[j]i的//最小质因子,所以primes[j]*i的最小质因子就是primes[j];//2)当有i%primes[j]0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是//prime[j]之后接着用st[primes[j1]*i]true去筛合数时就不是用最小质因子去更新了,因为i有最小//质因子primes[j]primes[j1],此时的primes[j1]不是primes[j1]*i的最小质因子此时就应该//退出循环避免之后重复进行筛选。if(i%primes[j]0) break;}}}试除法判断质数
输入n表示要判断的n个数接下来输入n个数判断其是否为质数
#includebits/stdc.h
using namespace std;
int n;
bool isprime(long long a){if(a1){return 0;}else if(a2){return 1;}for(int i2;ia/i;i){//不要用开方或者i*i开方函数较慢i*i会越界if(a%i0){return 0;}}return 1;
}
int main(){cinn;while(n--){long long a;cina;if(isprime(a)) coutYesendl;else coutNoendl;}
分解质因数
解题思路
x 的质因子最多只包含一个大于 根号x 的质数。如果有两个这两个因子的乘积就会大于 x矛盾。i 从 2 遍历到 根号x。 用 x / i如果余数为 0则 i 是一个质因子。s 表示质因子 i 的指数x / i 为 0则 s x x / i 。最后检查是否有大于 根号x 的质因子如果有输出。
#include iostream
#include algorithmusing namespace std;void divide(int x)
{for (int i 2; i x / i; i )//i x / i:防止越界速度大于 i sqrt(x)if (x % i 0)//i为底数{int s 0;//s为指数while (x % i 0) x / i, s ;cout i s endl;//输出}if (x 1) cout x 1 endl;//如果x还有剩余单独处理cout endl;
}
{
int main()
{int n;cin n;while (n -- ){int x;cin x;divide(x);}return 0;
}
