[2019.01.16] Running Time and Complexity

Problem

Objective 
Today we're learning about running time! Check out the Tutorial tab for learning materials and an instructional video!

Task 
A prime is a natural number greater than  that has no positive divisors other than  and itself. Given a number, , determine and print whether it's  or .

Note: If possible, try to come up with a  primality algorithm, or see what sort of optimizations you come up with for an  algorithm. Be sure to check out the Editorial after submitting your code!

Input Format

The first line contains an integer, , the number of test cases. 
Each of the  subsequent lines contains an integer, , to be tested for primality.

Constraints

Output Format

For each test case, print whether  is  or  on a new line.

Sample Input

3
12
5
7

Sample Output

Not prime
Prime
Prime

Explanation

Test Case 0: . 
 is divisible by numbers other than  and itself (i.e.: , , ), so we print  on a new line.

Test Case 1: . 
 is only divisible  and itself, so we print  on a new line.

Test Case 2: . 
 is only divisible  and itself, so we print  on a new line.

How I solved the problem

# 소수의 정의

소수는 n의 배수가 아니어야 한다.

입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다.

그러나 모두 나누어볼 필요없이, 루트 n 까지만 나누어서 떨어지면 소수가 아니다.

출처: http://marobiana.tistory.com/91 [Take Action]

# 이부분을 활용하여 알고리즘을 짜면 큰 수일 때도 Running Time에서 out되지 않음!

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

import java.io.*; import java.util.*;   public class Solution {       public static void main(String[] args) {         /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */         Scanner scan = new Scanner(System.in);         int number = scan.nextInt();         int[] divisionList = new int[number];           for (int i = 0; i < number; i++) {             divisionList[i] = scan.nextInt();         }           //is the number prime?         for (int i = 0; i < number; i++) {             int testNum = divisionList[i];             boolean isPrime = true;                          if (testNum == 1) {                 isPrime = false;             } else if (testNum == 2) {                 isPrime = true;             } else {                 for (int j = 2; j <= Math.sqrt(testNum); j++) {                     if (testNum % j == 0) {                         isPrime = false;                         break;                     }                 }             }               if (isPrime) {                 System.out.println("Prime");             } else{                 System.out.println("Not prime");             }                      }     } }     Colored by Color Scripter

cs

[출처 : https://www.hackerrank.com ]