Check if Number is Prime in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a prime number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

intermediate

Why do we only check divisors up to the square root of a number when testing for primality?

Because if a number has a divisor larger than its square root, it must also have a smaller divisor below the square root. So checking up to the square root is enough to find any divisor.

beginner

What is the simplest method to check if a number is prime?

Try dividing the number by all integers from 2 up to the number minus one. If none divide evenly, the number is prime.

beginner

What should you return if the number is less than 2 when checking for primality?

Return False because numbers less than 2 are not prime by definition.

advanced

How can you improve the efficiency of prime checking beyond checking all numbers up to sqrt(n)?

You can skip even numbers after checking 2, or use advanced methods like the Sieve of Eratosthenes or probabilistic tests for large numbers.

Which number is NOT a prime number?

A 2

B 3

C 4

D 5

4 is not prime because it can be divided evenly by 2.

When checking if a number n is prime, up to which number should you check for divisors?

A Square root of n

B n/2

C n+1

D n-1

Checking up to the square root of n is enough to find any divisor.

What should the function return for input 1 when checking primality?

A False

B Error

C True

D None

1 is not a prime number, so the function should return False.

Which of these is a quick way to skip unnecessary checks when testing primality?

A Check only even numbers

B Check only odd numbers after 2

C Check all numbers up to n

D Check only multiples of 3

After checking 2, you can skip even numbers because they are not prime.

What is the smallest prime number?

A 3

B 1

C 0

D 2

2 is the smallest prime number.

Explain how to check if a number is prime using a simple loop.

Think about dividing the number by smaller numbers to find factors.

Why is it unnecessary to check divisors beyond the square root of a number when testing primality?

Consider how multiplication pairs work.