3030: 초!!! 비!!! 상!!!!!
[만든사람 : lukanel]
문제 설명
잠을 자던 누리는 잠에서 깨어났다. 누리가 시계를 보자, 시계는 5교시 시작 시간을 한참 넘긴 1시 40분을 가리키고 있었다. 아이고 이를 어째. 기말이 끝나 정신줄을 놓아버린 누리는 그만 종이 치는 것도 모르고 기숙사에서 자버린 것이었다. 재빠르게 기숙사를 나와 학교로 달렸지만 아뿔싸! 승빈쌤께서는 이미 수업을 하고 계셨다. 교실 뒷문으로 몰래 들어가려던 누리는 스스로의 발에 걸려 그만 넘어지게 되고, 승빈쌤은 누리가 늦은 것을 발견하게 된다. 승빈쌤은 누리에게 게임을 하나 해서 이기면 무단지각 처리를 하지 않겠다고 하는데, 그 게임의 이름은 네제곱수 게임. 네제곱수 게임은 아래와 같다.
승빈쌤께서 소수를 몇 개 제시하면, 누리는 각 소수보다 4 작은 수 중 네제곱수인 수가 몇 개인지 판별해야 합니다. 만약 누리가 정답을 맞춘다면, 승빈쌤께서는 누리가 못 맞추게 하기 위해 더 많은 개수의 소수와 더 큰 소수들을 제시하게 됩니다.
누리가 이 불합리한 게임에서 이겨 무단지각 처리를 받지 않도록 도와주기 위한 코드를 짜보자.
#정수론 #수학
입력 설명
첫 줄에는 주어질 소수의 개수 n이 주어진다.
두 번째 줄부터 n+1번째 줄까지는 n개의 소수 $p_1,p_2,p_3…,p_n$ 이 입력된다. 이 소수들은 중복될 수 있다.
$(1≤n≤100000000,2≤p_i≤1000000007)$첫 줄에는 주어질 소수의 개수 n이 주어진다.
출력 설명
4를 빼면 네제곱수가 되는 소수의 개수를 출력한다.
입력 예시 Copy
3
2 5 7
출력 예시 Copy
1