Prime numbers in Range?

Question

I am writing a program to print the prime numbers in the given range, I know we can pick number one by one and try to see if it is divisible by 1 to n-1 or not. Do we have a better way to achieve this?

Answer 1

Try something like
Approach 1:
(a^n) mod n = a mod n where a and n are co prime then n is a prime number. (you know how to simplify the mod and ^ operations else use google)

Approach 2:
If number is not divisible by 2-sqrt(n) then also n is prime, this will save some iteration.

Comments

Let me try 1st seems to be promising...

Answer 2

You dont have to check every number's divisibility by 1 to n-1. Just check the divisibility by 2 to n/2

and moreover to reduce complexity(time and space both) n can be incremented by 2, once you are on odd number.. as even numbers cant be prime for sure.

Like prime numbers between 1-20 are
2,
3, [start incrementing n by 2 to check further and keep checking division of n from 2 to n/2],
5,
7,
9 (while checking division here from 2 to n/2, and you would find its not a prime),
11,
13,
15 (while checking division here from 2 to n/2, and you would find its not a prime)
17,
19
Note: 1 is neither prime nor composite

or
if your range starts from 1 - n always then
keep a list of checked prime numbers and later check the divisibility of any number by primes only (which are less than or equal to half of n).

just check out these approaches, if they might be useful.