Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
community creator

How to generate prime numbers in O(N^2)

Aarthi Reddy

4843485119643648### Prime number

A number that is divisible by one and itself is called a prime number. Examples of prime numbers are, 2,3,5,7,112,3,5,7,11, etc.

11 is not a prime number, and 22 is the only even prime number.

The code below shows how to generate primes smaller than or equal to n.

For example, when n is 66, prime numbers that are smaller than or equal to n would be 22,33, and 55

  • Step1: We need to check if the number is prime or not.

  • Step2: If the number is prime and less than or equal to the given number (n), print the number.

Code

The code below shows how to generate prime numbers smaller than or equal to a given number.

  1. Let number n=5 so that all prime numbers less than or equal to that number are printed.

  2. An empty list is taken to store the prime numbers less than or equal to the given number.

  3. Range function is used to check the sequence of integers from start value to stop value.

  4. i in for loop is used to access values in the range of 1, n+1 (to check the n value, we need to take n+1).

  5. Another for loop is taken with j variable to access values in the range of (2, i).

  6. Divisibility of the integer (i) is checked in the range of 2, i. If the integer is divisible, it will come out of the loop; else, the values are appended into the list.

  7. Finally, the list is printed that contains prime numbers less than or equal to the n value.

n=5
l=[]
for i in range(1,n+1):
    if(i>1):
        for j in range(2,i):
            if(i%j==0):
                break
        else:
            l.append(i)
print(l)

RELATED TAGS

python
community creator
RELATED COURSES

View all Courses

Keep Exploring