How to reduce the number of loop running during finding of prime number in the given range in java.

Number of loop running during the execution of program  makes our program delay, In this program we  try to reduce the number of loop running during  finding of prime number in the given range in java.

In First program we can see the number of loop running during finding the range of prime number between the number given.

Here’s the code for simple program to find the number of loop running and number of prime numbers are present in between the number given.

import java.util.Scanner
public class prime_number {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int n,lim,counter_loop=0,counter=0;
System.out.println(“Enter a number whithin it you want to check the no. of prime number is pesent=”);
n=s.nextInt();
outer: for(int i=2;i<=n;i++)
{
lim=(int) Math.sqrt(i);
for(int x=2;x<=lim;x++)
{
counter_loop++;
if(i%x==0)
continue outer;

}
counter++;
if(counter%30==0)
System.out.println();
System.out.print(i+” “);
}
System.out.println(“\nNumber of prime numbers in between this range=”+counter);
System.out.println(“\nNumber of time inner loop runs in between this range=”+counter_loop);
}
} Here we can see the number of loop running is 2113

Now we have to try to reduce the number of loop running, so here we go:-

Code for finding the numbers of prime number in the given range in minimum numbers of loop in java.

import java.util.Scanner;
public class range_prime {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
System.out.println(“Enter the range of no. you want to check the prime number in it=”);
int n,counter=2,counter_loop=0,t1=4,t2=4;
n=s.nextInt();
System.out.print(“2,3,”);                        // 2 and 3 are the prime numbers as we know so print it as it is.
outer:for(int x=5;x<=n;x=x+t1)              // outer loop starting from 5  as we print 2 and 3 earlier.

{
t1=6-t1;                                              //   from this we understand that  the  prime numbers are from 7,11,13 …etc
int limit=(int)Math.sqrt(x);                      it means the different between all these numbers are 2 and 4 which                                                                                    repeat itself  therefore the statement used here t=6-t1 and t2=6-t2.

if(x%2==0 || x%3==0)                     // The number which are divisible of 2 and 3 are not the prime numbers so
continue;                                              from here the numbers which are divisible by 2 and 3 are eliminated.
t2=4;                                                     it help to reduce the number of loop runs.
for(int i=5;i<=limit;i=i+t2

{
t2=6-t2;
counter_loop++;
if(x%i==0)                                         // If limit is divided then it is not the prime number so this condition send
continue outer;                                    the process from starting where it check  the another number by
}                                                                  increase the value by one this process repeat itself till limit.
counter++;
if(counter%30==0)
System.out.println();
System.out.print(x+”,”);
}
System.out.println(“\nNumber of prime numbers in between this range=”+counter);
System.out.println(“\nNumber of time inner loop runs in between this range=”+counter_loop);
}

}

Here’s the output:- Number of times loop runs=502.

Yeah..!! we had done it now we can see the difference as in first program the number of loop running is equal to 2113 but now it become only 502 times. So it’s  great achievement  and it is not possible to reduce more  number of times loop running during execution.