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






Prime Numbers

LEVEL:Beginner

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

oops

Login to see Discussion




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.

oops

Login to see Solution






     Recommended Questions      

Topic: Basic

Beginner

1. Sum of Two Numbers2. Swapping of Two Numberss3. Arithmetic Operations4. Leap Year5. Vowel or Consonant6. Prime Numbers7. Decimal to Binary 8. Swap first and last digit9. Reversing the Number10. Multiplication of Two numbers11. Factors of given number12. Armstrong Number13. Strong Number14. Perfect Number15. GCD of 3 Numbers.16. LCM of 3 Numbers.17. Decimal Number to Roman Number18. Print N numbers