Chào mọi người! Mình có 1 bài toán tin mà không AC được, mình có dùng sàng nt nhưng vân bị TLE. Mong mọi người giúp mình hướng giải để AC. Cảm ơn mọi người.
Code của mình:
// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
int a[101], n;
int prime[10001];
void sang(){
for(int i=0; i<=10000; i++)
prime[i]=1;
prime[0]=prime[1]=0;
for(int i=2; i<=100; i++){
if(prime[i]){
for(int j=i*i; j<=10000; j+=i)
prime[j]=0;
}
}
}
int tn(int n){
string s = to_string(n);
int l = 0, r=s.size()-1;
while(l<r){
if(s[l]!=s[r]) return 0;
}
return 1;
}
int cp(int n){
int x = sqrt(n);
if(x*x==n) return 1;
return 0;
}
int sum_prime(int n){
int sum = 0;
while(n){
sum += n%10;
n/=10;
}
if(prime[sum]) return 1;
return 0;
}
int main() {
// Write C++ code here
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
sang();
for(int i=0; i<n; i++) cin >> a[i];
int ans1=0, ans2=0, ans3=0, ans4=0;
for(int i=0; i<n; i++){
if(prime[a[i]]) ans1++;
if(tn(a[i])) ans2++;
if(cp(a[i])) ans3++;
if(sum_prime(a[i])) ans4++;
}
cout << ans1 << "\n" << ans2 << "\n" << ans3 << "\n" << ans4;
return 0;
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?