Write a Java code to check whether a number is prime or not with n root time complexity.

WHAT IS PRIME NUMBER ?

Prime numbers are whole numbers which can be divisible only by one and itself to get the remainder of zero. And for the number 1 which is not considered as a prime number.

PRIME NUMBER

A Java program to find the given numbers are prime or not.

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long a[] = new long[n]; for(int i=0; i<n; i++){ a[i] = sc.nextInt(); } for(int j=0; j<n; j++){ boolean prime = true; if(a[j] != 1){ for(int i=2; i*i <= a[j]; i++){ if(a[j] % i == 0 ) { prime = false; break; } } }else prime = false; if(!prime) System.out.println(a[j]+" is not a prime number"); else System.out.println(a[j]+" is a prime number"); } } }

OUTPUT

5 1010 100 97 137 17 1010 is not a prime number 100 is not a prime number 97 is a prime number 137 is a prime number 17 is a prime number

PRIME NUMBER 1 TO 100

A Java program to print prime numbers between 1 to 100.

import java.util.*; public class Solution { public static void main(String[] args) { int n = 100; boolean prime[] = new boolean[n+1]; Arrays.fill(prime, true); for(int j=1; j<=n; j++){ if(j != 1){ for(int i=2; i*i <= j; i++){ if(j % i == 0 ) { prime[j] = false; break; } } }else prime[j] = false; } int k=1; System.out.println("\nNon-prime Numbers are: "); while(k <=n) { if(!prime[k]) System.out.print(k+" "); else System.out.println("\nPrime Number: "+k); k++; } } }

OUTPUT

Non-prime Numbers are: 1 Prime Number: 2 Prime Number: 3 4 Prime Number: 5 6 Prime Number: 7 8 9 10 Prime Number: 11 12 Prime Number: 13 14 15 16 Prime Number: 17 18 Prime Number: 19 20 21 22 Prime Number: 23 24 25 26 27 28 Prime Number: 29 30 Prime Number: 31 32 33 34 35 36 Prime Number: 37 38 39 40 Prime Number: 41 42 Prime Number: 43 44 45 46 Prime Number: 47 48 49 50 51 52 Prime Number: 53 54 55 56 57 58 Prime Number: 59 60 Prime Number: 61 62 63 64 65 66 Prime Number: 67 68 69 70 Prime Number: 71 72 Prime Number: 73 74 75 76 77 78 Prime Number: 79 80 81 82 Prime Number: 83 84 85 86 87 88 Prime Number: 89 90 91 92 93 94 95 96 Prime Number: 97 98 99 100

FINDING PRIME NUMBERS BETWEEN GIVEN RANGE

A Java program to find prime numbers between the range given by the user.

import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Starting Number: "); int s = sc.nextInt(); System.out.println("Ending Number: "); int e = sc.nextInt(); boolean prime[] = new boolean[e-s+2]; Arrays.fill(prime, true); int m=0; for(int j=s; j<=e; j++){ if(j != 1){ for(int i=2; i*i <= j; i++){ if(j % i == 0 ) { prime[m] = false; break; } } }else prime[m] = false; m++; } int k=s; m=0; System.out.println("\nNon-prime Numbers are: "); while(k <=e) { if(!prime[m]) System.out.print(k+" "); else System.out.println("\nPrime Number: "+k); k++; m++; } } }

OUTPUT

Starting Number: 10 Ending Number: 20 Non-prime Numbers are: 10 Prime Number: 11 12 Prime Number: 13 14 15 16 Prime Number: 17 18 Prime Number: 19 20