资深守护
-
5076 输出质因数2经验值：800
题目描述 Description
输入一个正整数n（100<=n<=200000000)，从小到大输出n的所有质因数（质数本身也是它的一个质因数）。
输入描述 Input Description
一个正整数n
输出描述 Output Description
从小到大输出n的所有质因数
样例输入 Sample Input
18
样例输出 Sample Output
2 3
数据范围及提示 Data Size & Hint
50%的数据100<=n<=10000
100%的数据100000000<=n<=200000000
- #include<iostream>
- #include<cmath>
- using namespace std;
- int main() {
- int a;
- cin>>a;
- for(int i=2;i<=a;i++){
- if(a%i==0){
- int j;
- for(j=2;j<=sqrt(i);j++){
- if(i%j==0){
- break;
- }
- }
- if(j>sqrt(i)){
- cout<<i<<" ";
- }
- }
- }
- return 0;
- }
- 为什么超时了？急急急
鹿雨扬在2021-03-25 18:38:30追加了内容
#include<iostream>
#define MAXN 10005
using namespace std;
int a[MAXN];
int main()
{
int n;
cin>>n;
a[1]=1;
for(int i=2;i<=MAXN;i++){
if(a[i]==0){
for(int j=2*i;j<=MAXN;j+=i)
a[j]=1;
}
}
for(int i=1;i<=MAXN;i++){
if(a[i]==0&&n%i==0)
cout<<i<<" ";
}
return 0;
}
埃氏筛，哪错了
鹿雨扬在2021-03-26 14:13:31追加了内容
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
bool f(int x){
if(x==1){
return false;
}
for(int i=2;i<=sqrt(x);i++){
if(x%i==0){
return false;
}
}
return true;
}
int main(){
long long n;
cin>>n;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0&&f(i)){
cout<<i<<" ";
}
}
for(int i=2;i<=sqrt(n);i++){
if(n%i==0&&f(n/i)){
cout<<n/i<<" ";
}
}
return 0;
}
哪错了
中级守护
主函数主要代码：
for(int i=2;i<=sqrt(n);i++){ if(n%i==0&&f(i)){ cout<<i<<" "; } } for(int i=2;i<=sqrt(n);i++){ if(n%i==0&&f(n/i)){ cout<<n/i<<" "; } }
自定义函数：
bool f(int x){ if(x==1){ return false; } for(int i=2;i<=sqrt(x);i++){ if(x%i==0){ return false; } } return true; }
变量自己看
高级光能
改进方法
1.直接循环1~n，我就是这么过的;
2.这个代码在平方数会出错，第二个循环变成<sqrt(n);
蔡乐毅在2021-03-26 22:29:42追加了内容
1.说错了是循环2~n，if(n%i==0&&f(i)）
中级光能
这样不管怎么改都会超时，思路错了
可以先从循环2~n找出因数
再sort，然后循环判断这些因数中哪些是质数
cin>>n;
for(int i=2;i<=n;i++){
if(n%i==0){
a[++l]=i;
}
}
sort(a+1,a+l+1);
for(int i=1;i<=l;i++){
if(kx(a[i])) cout<<a[i]<<" ";
}
return 0;
//kx是判断质数的函数
//别忘了加火车头,#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(s)
//l初值设为0已AC
修练者
很奇怪！
高级光能
把int j;放在()里
资深守护
ding
新手启示者
1、scanf输入,printf输出
2、火车头
资深光能
埃氏筛法
周琪岳在2021-03-25 18:11:02追加了内容
筛出所有小于等于该数的质数后， 分解质因数时无需在for(i:1~sqrt(该数))一个一个判断了
