Skip to content

Latest commit

 

History

History
50 lines (32 loc) · 1.07 KB

README.md

File metadata and controls

50 lines (32 loc) · 1.07 KB
Raw

30 Days of Code - Day 25

To view solutions, see the file running-time-and-complexity.py in your text editor.

Day 25: Running Time and Complexity

Task:

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

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

Input Format

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

Constrains

  • 1 <= T <= 30
  • 1 <= n <= 2 * pow(10, 9)

Output Format

For each test case, print whether n is Prime or Not prime on a new line.

Sample Input

3
12
5
7

Sample Output

Not prime
Prime
Prime

Solution:

In running-time-and-complexity.py.

Return to navigation list