30 Day code challenge-python

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 is Prime or Not prime.

Note: If possible, try to come up with a primality algorithm, or see what sort of optimizations you come up with for an algorithm.

Sample input and output

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.

Output Format

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

Solution

Explanation

Line 1: Imports math module to calculate the square root of a number.

Line 2: Gets input from the user.

Line 8–10: Checks whether the input is greater than 2 and call the isPrime() function.

Line 3–7: Checks whether the number is prime or not.

Line 11–13: Prints Prime or Not prime based on isPrime() function.

Bonus Tip: O(log(n)) is the best time complexity comparing to others. However, it varies for different problems.

See you on day 26