埃拉托斯特尼筛法(sieve of Eratosthenes ) 是古希腊数学家埃拉托斯特尼发明的计算素数的方法。对于求解不大于n的所有素数,我们先找出sqrt(n)内的所有素数p1到pk,其中k = sqrt(n),依次剔除Pi的倍数,剩下的所有数都是素数。
具体操作如上述 图片所示。
C++实现
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<bool> isprime(n+5, true);
vector<int> ans;
for(int i = 2; i <= n; i++){
if(isprime[i]){
ans.push_back(i);
for(int j = i * i; j <= n; j += i)isprime[j] = false;
}
}
for(auto i : ans)cout<<i<<" ";
cout<<endl;
return 0;
}
整除问题
给定n,a求最大的k,使n!可以被a^k
整除但不能被a^(k+1)整除。
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main(){
int n, a, temp;
int ans = 0x7fffffff;
cin>>n>>a;
vector<bool> isprime(1010, true);
vector<int> prime;
map<int, int> primecntnp;
map<int, int> primecnta;
for(int i = 2; i <= 1010; i++){
if(isprime[i]){
prime.push_back(i);
primecntnp[i] = primecnta[i] = 0;
for(int j = i*i; j<= 1010; j += i)isprime[j] = false;
}
}
for(int i = 0; i < prime.size(); i++){
temp = n;
while(temp){
primecntnp[prime[i]] += temp/prime[i];
temp /= prime[i];
}
}
for(int i = 0; i < prime.size(); i++){
temp = a;
while(temp % prime[i] == 0){
primecnta[prime[i]]++;
temp /= prime[i];
}
if(primecnta[prime[i]] == 0)continue;
if(primecntnp[prime[i]]/primecnta[prime[i]] < ans)ans = primecntnp[prime[i]]/primecnta[prime[i]];
}
cout<<ans<<endl;
return 0;
}
更多内容访问omegaxyz.com
网站所有代码采用Apache 2.0授权
网站文章采用知识共享许可协议BY-NC-SA4.0授权
© 2019 • OmegaXYZ-版权所有 转载请注明出处
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)