The problem is from codeforces: http://www.codeforces.com/problemset/problem/230/B
The input of the numbers exceed a 4-byte integer, therefore, a long type (int64) should be used in Java. I feel like I haven’t coded Java for a while, therefore, I choose Java to solve this problem. The IDE I recommend is JCreator, which is simple to use yet powerful.
The brute-force straightforward solution is to check how many divisors each number has got, but this certainly is slow and may exceed the time limit. The other quicker math constraints of finding such numbers would be the following conditions.
- Must be larger than 1
- Must be a perfect square number, for example, 4, 9, 16, 25
- The square root of the number must be also a prime.
Checking the number being prime or not is easy, a brute-force solution listing the numbers up to its square root will be enough. However, as Java is slower compared to other programming languages such as C/C++, Delphi, the following will time out on the test 64.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | import java.util.Scanner; public class ACM { private static boolean Prime(long k) { long u = (long)Math.round(Math.sqrt(k)); for (long i = 2; i <= u; i ++) { if (k % i == 0) { return (false); } } return (true); } public static void main(String[] args) { Scanner in = new Scanner(System.in); long n = in.nextLong(); for (int i = 0; i < n; i ++) { long k = in.nextLong(); long u = (long)Math.sqrt(k); if ((k > 1) && (u * u == k) && Prime(u)) { System.out.println("YES"); } else { System.out.println("NO"); } } } } |
import java.util.Scanner;
public class ACM
{
private static boolean Prime(long k)
{
long u = (long)Math.round(Math.sqrt(k));
for (long i = 2; i <= u; i ++)
{
if (k % i == 0)
{
return (false);
}
}
return (true);
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
long n = in.nextLong();
for (int i = 0; i < n; i ++)
{
long k = in.nextLong();
long u = (long)Math.sqrt(k);
if ((k > 1) && (u * u == k) && Prime(u))
{
System.out.println("YES");
}
else
{
System.out.println("NO");
}
}
}
}The prime checking function can be slightly improved by jumping two numbers from 3. For example, instead of checking 2, 3, 4, 5, 6 … we can simply check 2, 3, 5, 7, 9 … which should be enough and a lot faster.
The following Java solution will pass all the test.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | //http://www.codeforces.com/problemset/problem/230/B //https://helloacm.com import java.util.Scanner; public class ACM { private static boolean Prime(long k) { long u = (long)Math.round(Math.sqrt(k)); long c = 1; for (long i = 2; i <= u; i += c) { if (k % i == 0) { return (false); } if (i == 3) { c = 2; } } return (true); } public static void main(String[] args) { Scanner in = new Scanner(System.in); long n = in.nextLong(); for (int i = 0; i < n; i ++) { long k = in.nextLong(); long u = (long)Math.sqrt(k); if ((k > 1) && (u * u == k) && Prime(u)) { System.out.println("YES"); } else { System.out.println("NO"); } } } } |
//http://www.codeforces.com/problemset/problem/230/B
//https://helloacm.com
import java.util.Scanner;
public class ACM
{
private static boolean Prime(long k)
{
long u = (long)Math.round(Math.sqrt(k));
long c = 1;
for (long i = 2; i <= u; i += c)
{
if (k % i == 0)
{
return (false);
}
if (i == 3)
{
c = 2;
}
}
return (true);
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
long n = in.nextLong();
for (int i = 0; i < n; i ++)
{
long k = in.nextLong();
long u = (long)Math.sqrt(k);
if ((k > 1) && (u * u == k) && Prime(u))
{
System.out.println("YES");
}
else
{
System.out.println("NO");
}
}
}
}–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Codeforces: A. Where do I Turn?
Next Post: Proof without Words: 1 + 2 + 3 + .. (n - 1) = Cn2
