Java >> Java tutorial >  >> Java

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


Java tag