+- BP Forums (https://bpforums.info)
+-- Forum: Archived Forums (https://bpforums.info/forumdisplay.php?fid=55)
+--- Forum: Archived Forums (https://bpforums.info/forumdisplay.php?fid=56)
+---- Forum: Java (https://bpforums.info/forumdisplay.php?fid=19)
+----- Forum: Code Snippets (https://bpforums.info/forumdisplay.php?fid=32)
+----- Thread: Prime Finder (/showthread.php?tid=756)
Prime Finder - WitherSlayer - 03-09-2013
This program will ask you for a number and then it will tell you if your number is prime or not.
[code2=java]import java.util.Scanner;
public class primeFinder {
static Scanner scanner = new Scanner(System.in);
public static void main(String[] args)
{
System.out.println("What number would you like to find if it is prime or not:");
int userNum = scanner.nextInt();
int i;
for (i = 2; i < userNum;i++)
{
int g = userNum % i;
if (g == 0)
{
System.out.println("Your number is not prime!");
break;
}
}
if(i == userNum)
{
System.out.println("Your number is prime!");
}
}
}[/code2]
Re: Prime Finder - brandonio21 - 03-10-2013
Awesome job! I love using programming languages to figure out the answers to trivial mathematical problems. Although your code snippet will work, there is actually a more efficient way to do it.
Since, when looking for factors of a number, for example let's look at 36, the highest number to actually look for is the square root of that number.
So, since the factors of 36 are:
1 2 3 4 6 9 12 18 36
As you can see, since we've already found factors of 36 (besides 1 and 36) before the square root of 36 (6), anything after that is negligable. This applies to any number. If there are no factors before (or equal to) the square root of the number, there are no factors at all.
So, your more efficient algorithm would look something like this:
[code2=java]import java.util.Scanner;
public class primeFinder {
static Scanner scanner = new Scanner(System.in);
public static void main(String[] args)
{
System.out.println("What number would you like to find if it is prime or not:");
int userNum = scanner.nextInt();
int i;
for (i = 2; i <= Math.sqrt(userNum); i++)
{
int g = userNum % i;
if (g == 0)
{
System.out.println("Your number is not prime!");
return;
}
}
System.out.println("Your number is prime!");
}
}[/code2]