1 Write a pseudo code for an algorithm that finds all prime

1) Write a pseudo code for an algorithm that finds all prime numbers that are less than or equal to n.

2) Analyze the worst-case time complexity of your algorithm in (1) by using Big-O notation.

Solution

1) Write a pseudo code for an algorithm that finds all prime numbers that are less than or equal to n.

1. Input n
2. for (x = 2 ... n )
3.   flag = TRUE
4.   for (i = 2 to x/2)
5.       if x%i = 0 then
6.           flag = FLASE
7.   if flag = TRUE then
8.       print x is prime

Explanation

1. Taking user input
2. Running from 2 to n and taking it in x
3. Initially assuming that x is Prime. So, setting flag to TRUE.
4. Checking from 2 to x/2
5. whether x is divisible any of the above numbers
6. setting flag to FALSE if so
7. If it is not divisible by any of the numbers, then
8. printing that the given number is prime