LESSON 137 OF 348 · LOOPS & CONDITIONALS

Prime Number in Rust

Practice

Given a non-negative integer n check if it is a prime number

Prime numbers are positive numbers greater than 1 that are divisible only by 1 and the number itself.

Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23

Example 1:

Input: n = 31
Output: true

Example 2:

Input: n = 6
Output: false
Explanation: 6 is divisible by 2 and 3.

Note:

Your algorithm should run in O(n) time and use O(1) space.

Hints:

Prime numbers are only divisible by the number 1 or itself. Let's reformulate this definition a little bit:
A number n is prime if and only if there is no such number d such that 1 < d < n and d is a divisor of n. Is this new definition more helpful?

We should iterate through each number d from 2 to n - 1 and check if d is a divisor of n.
If we find such a number, we can conclude that n is not prime and return false right away:

for each d : 2 -> n - 1:
	if d is divisor of n:
		return false

How do we check if d is divisor of n? When should we return true?

d is divisor of n (or n is a multiple of d) if and only if n % d == 0:

for each d : 2 -> n - 1:
	if n % d == 0:
		return false
return true

As you can see, if the for loop terminates and we reach the return true line of code, we know that we haven't found a divisor, so it's safe to say n is prime.

We have a for loop that performs exactly n - 2 iterations, thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).

STEP 1 OF 4

Guided

Ctrl + Enter to check