PDA

View Full Version : Prime Number Search using function


Navcool
Sep 11, 2013, 09:53 AM
In the main method, read the start and end integers. In a separate function, find the prime numbers that are available in between the start and end integers given in the main. Return the founded prime numbers back to the main (think we have to use arrays) and print it in the main by calling the function.
I have done part of the code like this but I don't know how to find the prime numbers between it.. pls correct the code!

import java.util.*;
public class primeno {
public static void main (String[]args)
{
Scanner in = new Scanner (System.in);
System.out.println("Enter the start and end numbers: ");
int a = in.nextInt();
int b = in.nextInt();
int[] result= search(a, b);
System.out.println(result);
}
public static int [] search (int x, int y) {
int count =0;
int len = y-x;
int [] arr = new int[len];
for (int i=x; i<=y; i++)
{
arr[count] = i;
count++;
for (int j=2; j<i; j++) {
int d = (i)%j;
if (d==0) {
//not a prime number
break;
}
}
}
return arr;
}
}

ebaines
Sep 11, 2013, 10:14 AM
I'm not a Java expert, but I will comment on your search routine. If I understand your technique for each candidate number between the start and end values of x and y you are trying a division first by 2 and seeing there is a remainder, then by 3, then by 4, etc up to the number.

Couple of thoughts: first, after testing division by 2 there is no need to test any other even numbers. So you can do the test with 2, then do a loop starting with 3 and incrementing by 2 to get only odd numbers for any further tests. Also there is no need to test any numbers larger than the square root of the number - if you haven't found any factors by then there won't be any. So for example in testing whether 53 is prime you only need to test values 2, 3, 5, and 7 - once you find that none of those divide 53 without a remainder there is no need to test any larger numbers. Making these will cut down on the compute time significantly - for the example of 53 your technique would run through 51 tests, as opposed to only four that are actually needed.