java - How is this below code identifying prime numbers -

java - How is this below code identifying prime numbers -

this code identifies prime numbers given number. if input, 7, returned arraylist have first 7 prime numbers in it.

public static arraylist<integer> calcprime(int inp) { arraylist<integer> arr = new arraylist<integer>(); arr.add(2); arr.add(3); int counter = 4; while(arr.size() < inp) { // 23 , 25 if(counter % 2 != 0 && counter%3 != 0) { int temp = 4; while(temp*temp <= counter) { if(counter % temp == 0) break; temp ++; } if(temp*temp > counter) { arr.add(counter); } } counter++; } homecoming arr; }

my question this. understand code filtering numbers divisible 2 , 3. other numbers, 23 or 25, relying on squares of numbers 4.

i want know how achieving goal. please help me understanding this.

the bit that's doing checking this:

if(counter % temp == 0) break;

it's not relying on squares of numbers @ all. that's telling when stop checking numbers.

first initial set up. knows 2 , 3 primes, adds them list.

then, starting @ 4, checks see if number prime. if is, adds array, if it's not skips out , checks next number.

so "checks see if number prime" done by: first checking if it's divisible 2 or divisible 3:

if(counter % 2 != 0 && counter%3 != 0)

then, starting @ 4 again, doing same check: potential prime (counter) divisible number (temp) ?

if(counter % temp == 0)

if that's case, it's not prime number break command , checks next counter see if that's prime.

if counter not divisible temp increments temp , checks again. when temp big it's not worth checking if it's factor more, algorithm knows counter prime, , adds list.

the temp*temp bit because when it's checking see if number prime, doesn't have check of numbers counter. if temp*temp greater our target, temp factor, other factor has less temp, , has been checked.

java primes