埃拉托斯特尼筛法（sieve of Eratosthenes ） 是古希腊数学家埃拉托斯特尼发明的计算素数的方法。对于求解不大于n的所有素数，我们先找出sqrt(n)内的所有素数p1到pk，其中k = sqrt(n)，依次剔除Pi的倍数，剩下的所有数都是素数。
具体操作如上述 图片所示。
C++实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#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)整除。
输入描述
|
1 |
两个整数n(2<=n<=1000)，a(2<=a<=1000) |
输出描述
|
1 |
一个整数. |
示例1
输入
|
1 |
555 12 |
输出
|
1 |
274 |
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#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; //存储n!的质因子的指数 map<int, int> primecnta; //存储a的质因子的指数 for(int i = 2; i <= 1010; i++){ //采用素数筛选出前1010个数中的素数，并将map初始化 if(isprime[i]){ prime.push_back(i); primecntnp[i] = primecnta[i] = 0; for(int j = i*i; j<= 1010; j += i)isprime[j] = false; } } //4! = 24 = 1*2*3*4 = 2*2*2*3 for(int i = 0; i < prime.size(); i++){ //对n!进行因式分解 temp = n; while(temp){ //按照p、p*p、p*p*p来进行因式分解 primecntnp[prime[i]] += temp/prime[i]; temp /= prime[i]; } } for(int i = 0; i < prime.size(); i++){ //对a进行因式分解 temp = a; while(temp % prime[i] == 0){ primecnta[prime[i]]++; temp /= prime[i]; } if(primecnta[prime[i]] == 0)continue; //a里面不存在的则无法提供 if(primecntnp[prime[i]]/primecnta[prime[i]] < ans)ans = primecntnp[prime[i]]/primecnta[prime[i]]; }//找到最小的指数，便是最大的k值 cout<<ans<<endl; return 0; } /* 555 12 274 */ |
