Array ( [0] => [1] => questions [2] => Basic [3] => Prime-Numbers ) Basic | Prime Numbers | THE INQUISITIVE

Prime Numbers

Description

Given a integers N. You have to find all the prime number below that given number.

Input Format

First line contains a integers N.

Output Format

Print every prime number below N.

Example 1:

Input
`5`
Output
`2 3`
Example 2:

Input
`10`
Output
`2 3 5 7`
Example 3:

Input
`20`
Output
`2 3 5 7 11 13 17 19`

Approach

Approach 1: Iterating upto n

Step-i) create an empty string
Step-ii) run the loop from i=2 to i<= given number
Step-iii) if remainder of division given_number/i is 0 append i to the string
Step-iv) return the string

Time Complexity: O(n)
Space Complexity: O(1)

Approach 2: Iterating upto n/2

Step-i) create an empty string
Step-ii) run the loop from i=2 to i<= given number/2
Step-iii) if remainder of division given_number/i is 0 append i to the string
Step-iv) return the string

Time Complexity: O(n/2)
Space Complexity: O(1)

Approach 3: Iterating upto sqrt(n)

Step-i) create an empty string
Step-ii) run the loop from i=2 to i<= sqrt(n)
Step-iii) if remainder of division given_number/i is 0 append i to the string
Step-iv) return the string

Time Complexity: O(sqrt(n))
Space Complexity: O(1)

Approach 4: Using Sieve approach

Step-i)create array of size n
Step-ii) initialize the array with true
Step-iii) initialize i to 2
Step-iv) if element at index i is true then value at index equal to multiples of i change to false
Step-v) increment i by one value
Step-vi) repeat steps iv and v till i*i is less than the given number
Step-vii) create a empty string answer
Step-viii) append all the index whose value is true
Step-ix) return the string

Time Complexity: O(nloglogn)
Space Complexity:O(1)

Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.