What is Prime number?
As per definition, Number which is greater than 1 and has only 1 divider which is itself is called Prime number. Other numbers are called Composite Number. Let’s take a look: 3, 5, 7, 11, 13 are prime numbers.
Sometime back I’ve written an article on how to print fibonacci series. In this tutorial we will go over below points:
- Two different ways to determine a prime number in Java
- Best way to generate prime number in Java
Let’s get started:
- Create class CrunchifyIsPrimeAndGeneratePrime.java
- create crunchifyIsPrimeNumber(int) to check if number is prime?
- create crunchifyIsPrimeNumberMethod2(int) to check number is prime or not using diff approach
- crunchifyGeneratePrimeNumbers(int) generates prime number between 2 and provided number
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
package com.crunchify.tutorials; /** * @author Crunchify.com * */ public class CrunchifyIsPrimeAndGeneratePrime { public static void main(String args[]) { System.out.println(crunchifyIsPrimeNumber(11)); System.out.println(crunchifyIsPrimeNumber(22)); System.out.println(crunchifyIsPrimeNumber(37)); System.out.println(crunchifyIsPrimeNumber(7)); System.out.println("\n"); System.out.println(crunchifyIsPrimeNumberMethod2(3)); System.out.println(crunchifyIsPrimeNumberMethod2(43)); System.out.println(crunchifyIsPrimeNumberMethod2(23)); System.out.println(crunchifyIsPrimeNumberMethod2(88)); // Here 120 is an upper limit crunchifyGeneratePrimeNumbers(120); } private static boolean crunchifyIsPrimeNumber(int crunchifyNumber) { System.out.println("Prime check started for number: " + crunchifyNumber); // Loop starts from 2 for (int i = 2; i <= crunchifyNumber / 2; i++) { if (crunchifyNumber % i == 0) { return false; } } return true; } // Another way to check if Number is Prime public static boolean crunchifyIsPrimeNumberMethod2(int crunchifyNumber) { System.out.println("Prime check started for number: " + crunchifyNumber); boolean crunchifyPrime = true; int limit = (int) Math.sqrt(crunchifyNumber); for (int i = 2; i <= limit; i++) { if (crunchifyNumber % i == 0) { crunchifyPrime = false; break; } } return crunchifyPrime; } public static void crunchifyGeneratePrimeNumbers(int crunchifyUpperLimit) { System.out.println("\nGenerating all prime number between 2 to " + crunchifyUpperLimit); for (int i = 2; i < crunchifyUpperLimit; i++) { boolean crunchifyIsPrime = true; // check to see if the number is prime for (int j = 2; j < i; j++) { if (i % j == 0) { crunchifyIsPrime = false; break; } } // print the number if (crunchifyIsPrime) System.out.print(i + " "); } } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Prime check started for number: 11 true Prime check started for number: 22 false Prime check started for number: 37 true Prime check started for number: 7 true Prime check started for number: 3 true Prime check started for number: 43 true Prime check started for number: 23 true Prime check started for number: 88 false Generating all prime number between 2 to 120 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 |
Would the code still work if you were using long instead of int for crunchifyNumber in the second method?
Long has a minimum value of 0 and a maximum value of 264-1. Use this data type when you need a range of values wider than those provided by int.
Great post!
You could speed up the algorithm to check a number even more if you start the loop at 3 and set the step size to 2 so you skip all even numbers. Especially for large numbers this should improve the performance.
Great point. Would be nice if you share a code if that’s handy.
sure, here you go:
I edited your method2 and renamed it to method3. The only thing I changed is the head of the for loop.
public static boolean crunchifyIsPrimeNumberMethod3(int crunchifyNumber) {
System.out.println(“Prime check started for number: ” + crunchifyNumber);
boolean crunchifyPrime = true;
int limit = (int) Math.sqrt(crunchifyNumber);
for (int i = 3; i <= limit; i+=2) {
if (crunchifyNumber % i == 0) {
crunchifyPrime = false;
break;
}
}
return crunchifyPrime;
}
Unfortunately I can't indent the code so it looks not that pretty. But it should do it.
Thanks much for sharing a code. I’ll take a look this during weekend and update.