Primtalsprogram i Java
I dette indlæg vil vi udvikle et primtalsprogram i Java, et program til at kontrollere primtal i Java, og et javaprogram til at udskrive primtal mellem to tal.
Et naturligt tal, som kun har to faktorer ( 1 og sig selv ), kaldes et primtal. For eksempel - 5 er et primtal, fordi det kun har to faktorer 1 og 5. På samme måde er 9 ikke et primtal, fordi det har mere end 2 faktorer, der er 1, 3 og 9.
Simpelt primtalsprogram i Java
At udvikle et program til at kontrollere det givne tal er et primtal eller ej i java; For det første bør du vide, hvordan du udvikler et Java-program for at finde ud af alle faktorer af et tal. For hvis et tal har mere end 2 faktorer, er det kun et primtal. Alle negative tal, 0 og 1, er ikke primtal.
Primtalsprogram i Java ved hjælp af for loop
import java.util.Scanner;
public class SimplePrimeNoProgram {
public static boolean isPrime(int number){
// All negative numbers, 0 and 1
// are not a prime number
if(number<=1) return false;
// check for remaining
for(int i=2; i<number; i++)
if(number%i == 0)
return false;
return true;
}
public static void main(String[] args) {
// declare variables
int number = 0;
boolean flag = false;
// create Scanner class object
Scanner scan = new Scanner(System.in);
// read number
System.out.print("Enter a number:: ");
number = scan.nextInt();
// check number is prime number or not
flag = isPrime(number);
// display result
if(flag) // true
System.out.println(number+
" is a prime number");
else
System.out.println(number+
" is not a prime number");
// close Scanner class object
scan.close();
}
}
Output for forskellige testcases:-
Indtast et tal::11
11 er et primtal
Indtast et tal::9
9 er ikke et primtal
Tidskompleksiteten af denne løsning er O(n) .
Se også:- Specialnummer, Magisk nummer, Armstrong-nummer, Perfekt nummer, Evil Number, Spionnummer, Sunny-nummer i Java
Brug while-løkke
Det tidligere primtalsprogram i java blev udviklet ved hjælp af for loop, men vi kan også bruge en while loop i stedet for for loop. Brug nedenstående metode i det forrige program.
Primtalsmetode i Java ved hjælp af while-løkke
public static boolean isPrime(int number) {
// declare variables
int i = 2;
// negative numbers, 0 and 1
// are not a prime number
if(number<=1) return false;
// loop to repeat the process
while(i<number) {
if(number%i == 0)
return false;
i++;
}
return true;
}
Tidskompleksiteten af denne løsning er O(n) .
Program til at kontrollere primtal i Java
Ovenstående programmer er rigtige og giver korrekt output, men de giver mindre ydeevne, deres tidskompleksitet var O(n). Vi kan optimere ovenstående programmer.
Der er nogle punkter, vi bør huske på for at udvikle det bedste prime-program i java, som vil give høj ydeevne.
- Alle negative tal, 0 og 1, er ikke primtal.
- 2 er det eneste lige primtal.
- Hvert primtal (undtagen 2 og 3) kan præsenteres i form af 6n+1 eller 6n-1
- 2 og 3 er de eneste to på hinanden følgende naturlige tal, som også er primtal.
Vi kan udføre følgende optimeringer,
1) I stedet for at markere indtil i=1 for at nummerere, bør vi kun kontrollere op til √n.
I indlægget find faktorer i java lærte vi, at vi kan bruge sqrt()
metode til at begrænse iterationen, og divider tallet med iteratorvariabel for at finde de faktorer, der er større end kvadratrodsværdien af tallet. Koden kan skrives som,
for(….; i<=Math.sqrt(number); ….) {
// logic
}
2) Alle primtal undtagen 2 og 3 er i form af 6k ± 1. Se:- Primalitetstest
Da alle heltal kan udtrykkes som (6k+i) for nogle heltal k og for i=-1,0,1,2,3 eller 4 (Her skrives 5 som -1). Da de heltal repræsenteret som 6k+0, 6k+2 og 6k+4 er lige tal og delelige med to, så de kan ikke være et primtal. Heltallene repræsenteret som 6k+3 vil være delelige med 3, så det kan heller ikke være et primtal. Nu kan de resterende heltal, der er repræsenteret som 6k+1 og 6k-1, være et primtal eller et sammensat tal. Så vi skal kun kontrollere for tal, der er repræsenteret som 6k ± 1.
Derfor er det bedre at kontrollere, at tal er deleligt med 2 eller 3, hvis ja, så er det ikke et primtal.
if(number%2==0 || number%3==0)
return false;
Logikken for primtal
Java-metodekode til at kontrollere det givne tal er et primtal eller ej
public static boolean isPrime(int number) {
// negative numbers, 0 and 1 are
// not a prime number
if( number <= 1 ) return false;
// 2 and 3 are prime numbers
if( number <= 3 ) return true;
// numbers divisible by 2 and 3
// are not prime number
if(number%2==0 || number%3==0)
return false;
// logic for remaining numbers
for(int i=5; i<=Math.sqrt(number); i=i+6) {
// 6k+1 => number%i
// 6k-1 => number % (i+2)
if(number%i == 0 || number%(i+2) == 0)
return false;
}
// if all above conditions are not satisfied
return true;
}
Tidskompleksiteten for denne metode er O(√n) .
Java-program
I checkPrime()
metode, vi brugte til loop til at kontrollere primtal i java, men vi kan også bruge en while eller do-while loop. Nu, baseret på denne metode, vil vi udvikle et primtalsprogram i java ved hjælp af Scanneren.
import java.util.Scanner;
public class PrimeNumber {
public static boolean isPrime(int number){
// negative numbers, 0 and 1 are
// not a prime number
if( number <= 1 ) return false;
// 2 and 3 are prime numbers
if( number <= 3 ) return true;
// numbers divisible by 2 and 3
// are not prime number
if(number%2==0 || number%3==0)
return false;
// logic for remaining numbers
for(int i=5; i<=Math.sqrt(number); i=i+6){
if(number%i == 0 || number%(i+2) == 0)
return false;
}
return true;
}
public static void main(String[] args) {
// declare variables
int number = 0;
boolean isPrime = false;
// create Scanner class object
Scanner scan = new Scanner(System.in);
// read number
System.out.print("Enter a number:: ");
number = scan.nextInt();
// check number is prime number or not
isPrime = isPrime(number);
// display result
if(isPrime) // true
System.out.println(number+
" is a prime number");
else
System.out.println(number+
" is not a prime number");
// close Scanner class object
scan.close();
}
}
Output:-
Indtast et tal::11
11 er et primtal
Indtast et tal::9
9 er ikke et primtal
Tidskompleksiteten for denne løsning er O(√n) .
Primtal ved brug af rekursion i Java
import java.util.Scanner;
public class PrimeNumber {
public static boolean isPrime(int number, int i){
// negative numbers, 0 and 1 are
// not a prime number
if( number <= 2 )
return (number != 2) ? false : true;
if( number % i == 0 ) return false;
if( i*i > number ) return true;
// check for the next
return isPrime(number, i+1);
}
public static void main(String[] args) {
// declare variables
int number = 0;
boolean flag = false;
// create Scanner class object
Scanner scan = new Scanner(System.in);
// read number
System.out.print("Enter a number:: ");
number = scan.nextInt();
// check number is prime number or not
flag = isPrime(number, 2);
// display result
if(flag) // true
System.out.println(number+
" is a prime number");
else
System.out.println(number+
" is not a prime number");
// close Scanner class object
scan.close();
}
}
Program til at udskrive de første 10 primtal i Java
public class PrintPrimeNumber {
public static boolean isPrime(int number) {
/* Negative numbers, 0 and 1
* are not a prime number
*
* Even numbers (except 2) are
* also not a prime number
*/
if(number == 2) return true;
else if(number<=1 || number%2==0)
return false;
// logic for remaining numbers
for(int i=3; i<=Math.sqrt(number); i++){
if(number%i == 0) return false;
}
return true;
}
public static void main(String[] args) {
System.out.println(
"First 10 prime numbers in Java are::");
// variables
int i=1, count=0;
// loop to repeat the process
while(count<10) {
if(isPrime(i)) {
System.out.print( i + " ");
count++;
}
i++;
}
}
}
Output:-
De første 10 primtal i Java er::2 3 5 7 11 13 17 19 23 29
Java-program til at udskrive primtal mellem to givne tal
Det forrige program udskriver de første 10 primtal i Java. I lighed med det program kan vi skrive et program til at udskrive primtal mellem to tal for eksempel:- program til at udskrive primtal fra 1 til 100 i java.
import java.util.Scanner;
public class PrimeNumberInRange {
public static boolean isPrime(int number) {
/* Negative numbers, 0 and 1
* are not a prime number
*
* Even numbers (except 2) are
* also not a prime number
*/
if(number == 2) return true;
else if(number<=1 || number%2==0)
return false;
// logic for remaining numbers
for(int i=3; i<=Math.sqrt(number); i++) {
if(number%i == 0) return false;
}
return true;
}
public static void main(String[] args) {
// declare variables
int minRange , maxRange;
// create Scanner class object
Scanner scan = new Scanner(System.in);
// read inputs
System.out.print("Enter min Range value::");
minRange = scan.nextInt();
System.out.print("Enter max Range value::");
maxRange = scan.nextInt();
// check in range
System.out.println("Prime numbers from "+
minRange+" to "+maxRange+" :: ");
for(int i = minRange; i<= maxRange; i++)
if(isPrime(i))
System.out.print( i + " ");
// close Scanner class object
scan.close();
}
}
Outputtet for forskellige testcases er:-
Indtast min. områdeværdi::1
Indtast maks. områdeværdi::100
Primtal fra 1 til 100::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
Indtast min. områdeværdi::100
Indtast maks. områdeværdi::200
Primtal fra 100 til 200::101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199