10.26-东塘404-J1R(2):埃氏筛

//埃氏筛：
//标记当前数是合数(1)/质数(0)
//默认一开始所有数都是指数
bool isp[100000010];
void ashpick(int n){  //筛出1~n之间的所有数
  isp[0]=isp[1]=1;  //0和1都不是质数
  for(int i=1;i<=n;i++){
    if(isp[i]==0){  //找到一个质数i
      for(int j=i*2;j<=n;j+=i){  //拿i去筛掉他的所有倍数
        isp[j]=1;  //标记成不是质数
      }
    } 
  } 
} 

for(int i=2;i<=n/i;i++){
  int cnt=0;
  while(n%i==0){
    cnt++;
    n/=i;
  }
  if(cnt%2==1){
    x*=i;		
  }
}

#include<bits/stdc++.h>
using namespace std;
long long n;
int main(){
	cin>>n;
	long long x=1;
	for(int i=2;i<=n/i;i++){
		int cnt=0;
 		while(n%i==0){
    		cnt++;
   			n/=i;
  		}
  		if(cnt%2==1){
		  	x*=i;		
		}
	}
	if(n>1)x*=n;
	cout<<x;
	return 0;
} 

for(int xx=1;xx<=n;xx++){
	int x=xx;
	for(int i=2;i<=x/i;i++){
	 	while(x%i==0){
	 		cnt[i]++;
	   		x/=i;
		}
	}
	if(x>1)cnt[x]++;
}
for(int i=1;i<=1000000;i++){
	if(cnt[i]){
		cout<<i<<' '<<cnt[i]<<endl;
	}
}

#include<bits/stdc++.h>
using namespace std;
long long n,cnt[1000010];
int main(){
	cin>>n;
    for(int xx=1;xx<=n;xx++){
    	int x=xx;
    	for(int i=2;i<=x/i;i++){
    	 	while(x%i==0){
    	 		cnt[i]++;
    	   		x/=i;
    		}
    	}
    	if(x>1)cnt[x]++;
    }
    for(int i=1;i<=1000000;i++){
    	if(cnt[i]){
    		cout<<i<<' '<<cnt[i]<<endl;
    	}
    }
	return 0;	
}

while(t--){
    	long long n;
		cin>>n;
		if(is_prime(n)){
			cout<<n<<endl;
			continue;
		}
		for(long long i=2;i<=n/i;i++){
			if(n%i==0){
				cout<<i<<endl;
				break;
			}
		}
	}

#include<bits/stdc++.h>
using namespace std;
long long is_prime(long long n){
  if(n<=1){
    return 0;
  }
  for(long long i=2;i<=n/i;i++){
    if(n%i==0){
      return 0;
    }
  }
  return 1;
}
long long t; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
    	long long n;
		cin>>n;
		if(is_prime(n)){
			cout<<n<<endl;
			continue;
		}
		for(long long i=2;i<=n/i;i++){
			if(n%i==0){
				cout<<i<<endl;
				break;
			}
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
bool isp[100000000];
void ashpick(int n){
  isp[0]=isp[1]=1;
  for(int i=2;i<=n;i++){
  	if(isp[i]==0){
  		for(int j=i*2;j<=n;j+=i){
  			isp[j]=1;
		}	
	}
  }
}
long long n;
int main(){
	cin>>n;
	ashpick(n);
	long long ans=0;
	for(int i=1;i<=n;i++){
		if(isp[i]==0)ans++;
	}
	cout<<ans;
	return 0;
}