Skip to content

Instantly share code, notes, and snippets.

@arsho

arsho/codeforces_230_b.cpp

Last active March 28, 2022 18:59
Show Gist options
  • Save arsho/5281f669e7c18653c31cebf83ed30dee to your computer and use it in GitHub Desktop.
Save arsho/5281f669e7c18653c31cebf83ed30dee to your computer and use it in GitHub Desktop.
Download ZIP
Codeforces 230B solution
Raw
codeforces_230_b.cpp
/*
# OJ : Codeforces
# Contest : 230
# Problem : B. T-primes
# URL : http://codeforces.com/contest/230/problem/B
# Date : 17/06/2017
# Author : arsho
# Verdict : Accepted
# Time : 934 ms
# Memory : 7800 KB
*/
#include <bits/stdc++.h>
using namespace std;
#define LIMIT 1000000
long long i, j;
long long prime_flag[LIMIT];
void calculate_prime_flag(){
prime_flag[0] = prime_flag[1] = 1;
for(i=2;i<LIMIT;i++){
if (prime_flag[i]==0){
for(j=i*i;j<LIMIT;j+=i){
prime_flag[j] = 1;
}
}
}
}
int check_perfect_square(long long n){
double sqrt_n = sqrt(n);
if(sqrt_n == int(sqrt_n)){
return 1;
}
else{
return 0;
}
}
int main(){
calculate_prime_flag();
long long total_numbers, n;
cin>>total_numbers;
for(i=0;i<total_numbers;i++){
cin>>n;
if (n==4){
cout<<"YES"<<endl;
}
else if (n%2==0){
cout<<"NO"<<endl;
}
else if(check_perfect_square(n)==1 && prime_flag[int(sqrt(n))]==0){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
}
Raw
codeforces_230_b.py
# OJ : Codeforces
# Contest : 230
# Problem : B. T-primes
# URL : http://codeforces.com/contest/230/problem/B
# Date : 17/06/2017
# Author : arsho
# Verdict : Accepted
# Time : 1620 ms
# Memory : 13000 KB
'''
The problem is to find if a number is a T prime.
A number is called a T prime if it has only 3 divisors.
Solution:
=========
A number is a T prime if it is a perfect square
and its square root is a prime number.
4 is the only even number which is a T prime number.
'''
limit = 1000000
def calculate_prime_flag_for_each_number_upto_limit():
prime_flag = [True] * limit
prime_flag[0] = prime_flag[1] = False
for i in range(2,limit):
if prime_flag[i] == True:
for j in range(i*i, limit, i):
prime_flag[j] = False
return prime_flag
def check_if_a_number_is_t_prime(n):
if n == 4:
return True
if n < 4 or n%2==0:
return False
sqrt_n = n**0.5
if sqrt_n==int(sqrt_n):
if prime_flag[int(sqrt_n)] == True:
return True
return False
prime_flag = calculate_prime_flag_for_each_number_upto_limit()
total_numbers = int(input())
input_array = list(map(int,input().split()))
for i in input_array:
if check_if_a_number_is_t_prime(i)==True:
print("YES")
else:
print("NO")
@dhiraj-ms
Copy link

can you explain me please what logic is behind this in your first code..

@prabhatsoni99
Copy link

All numbers have atleast 2 factors (1 and the number itself). The only case where a number has a 3rd factor when a factor * factor = number. Or factor = sqrt(number)

@Anirgb00
Copy link

Anirgb00 commented Apr 27, 2020 •
edited
Loading

thx for explainations even though it was too late for first one helped others..

@Vishal-Karki
Copy link

Only those numbers are T-prime which are perfect sq and their sq. root is also prime

  • By using the sieve of Eratosthenes algorithm, we are calculating the prime numbers up to 1000000 and checking they are prime or not
  • Also checking that number is perfect Square
    By fulfilling these two conditions we can check for T-prime number

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment