素数筛耗时太久,求助(关注自由)
查看原帖
素数筛耗时太久,求助(关注自由)
1004343
wangjingtian1楼主2024/7/22 20:41

HELP

我辛辛苦苦调了那么久,败在素数筛上
帮个忙
#include <bits/stdc++.h>
using namespace std;
int A[1000000];
int B[1000000];
int k=0;
void prime_number(){
	int cnt=0;
	bool b=0;
	for(int i=2;i<=1000000;i++){
		for(int j=2;j<i;j++){
			if(i%j==0){
				b=1;
				break;
			}
		}
		if(b==0){
			A[cnt++]=i;
		}
	}
	return ;
	
	
}
int main(){
	
	int n;
	cin>>n;
	int b;prime_number();
	for(int i=0;i<n;i++){
		cin>>b;
		
		int l=0;
		int ans=0;
		while(b!=1){
			if(b % A[l] == 0){
				b /= A[l];
			}else{
				l++;
				ans++;
				cout<<A[l]<<endl;
			}
			//cout<<b<<endl;
			if(ans>2){
				break;
			}
		}
		if(ans==2){
			cout<<1<<endl;
		}else{
			cout<<0<<endl;
		}
	} 
}

再次求助

2024/7/22 20:41
加载中...