HackkerRank: Time Complexity:Primality

1. Link to the problem

• https://www.hackerrank.com/challenges/ctci-big-o/problem

---

2. Point

• brute force 로 문제를 풀면 O(n) 이 나온다.
• U (Unnecessary Work) Math.sqrt 사용하여 불필요한 작업을 제거했다.
• Math.sqrt 를 사용한다는 의미는 n 의 루트를 씌움으로써 루트 n 이후의 불필요한 작업은 제거한 것이다. 왜냐면 루트 n * 루트 n 은 n 이기 때문이다.
• 위 결론에 따라 루트 n 이 prime 인지만 판별하면 되고, 루트 n 의 정수를 추출해서 i = 2 ~ 추출된 정수로 나눈다면 답이 나온다.

---

3. Source

public static void main(String [] args)
{
	Scanner in = new Scanner(System.in);
	int p = in.nextInt();
	for (int pItr = 0 ; pItr < p ; pItr++)
	{
		int n = in.nextInt();
	    String result = solve(n);
	    System.out.println(result);
	}
}
	
public static String solve(int n)
{	
	if (n == 1)
		return "Not prime";
	else
	{
		int l = (int) Math.sqrt(n);
		for (int i = 2 ; i <= l ; i++)
		{
			if (n % i == 0)
				return "Not prime";
		}
	}
	return "Prime";
}