Manera eficiente de calcular la suma de todos los primos entre un rango -- java camp codereview Relacionados El problema

Efficient way to calculate the sum of all primes between a range


5
vote

problema

Español

problema

Estoy tratando de escribir un código en el que se hacen las preguntas Q y cada pregunta contiene dos números A y B . Para cada pregunta, tengo que encontrar la suma de todos los números primos entre los enteros A y B (inclusive). He escrito un programa que funciona, pero no es lo suficientemente rápido para aprobar todas las restricciones. ¿Hay alguna manera de mejorar la eficiencia de mi código?

restricciones

1≤q≤10 ^ 5

1≤a≤b≤10 ^ 5

Límite de tiempo: 0.6s

  import java.io.*; import java.util.*;  public class sumofprimes{     static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));     static StringTokenizer st;     static boolean isPrime(int n){          if(n==1)return false;          for (int i=2; i*i<=n; i++)              if (n%i==0) return false;         return true;      }         static int sum(int a, int b){          int sum=0;          for(int i=b; i>=a; i--) {              boolean prime=isPrime(i);              if(prime) sum+=i;         }          return sum;      }      public static void main(String[] args)throws IOException{          int q=readInt();         for(int i=0; i<q; i++){             int a=readInt(), b=readInt();              System.out.println(sum(a,b));         }     }      static String next () throws IOException {         while (st == null || !st.hasMoreTokens())            st = new StringTokenizer(br.readLine().trim());     return st.nextToken();     }     static int readInt () throws IOException {     return Integer.parseInt(next());     } }   
Original en ingles

Problem

I'm trying to write a code in which Q questions are asked and each question contains two numbers A and B. For each question, I have to find the sum of all primes between integers A and B (inclusive). I've written a program that works, but it isn't fast enough to pass all the restrictions. Is there any way to improve the efficiency of my code?

Restrictions

1xe2x89xa4Qxe2x89xa410^5

1xe2x89xa4Axe2x89xa4Bxe2x89xa410^5

Time limit: 0.6s

import java.io.*; import java.util.*;  public class sumofprimes{     static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));     static StringTokenizer st;     static boolean isPrime(int n){          if(n==1)return false;          for (int i=2; i*i<=n; i++)              if (n%i==0) return false;         return true;      }         static int sum(int a, int b){          int sum=0;          for(int i=b; i>=a; i--) {              boolean prime=isPrime(i);              if(prime) sum+=i;         }          return sum;      }      public static void main(String[] args)throws IOException{          int q=readInt();         for(int i=0; i<q; i++){             int a=readInt(), b=readInt();              System.out.println(sum(a,b));         }     }      static String next () throws IOException {         while (st == null || !st.hasMoreTokens())            st = new StringTokenizer(br.readLine().trim());     return st.nextToken();     }     static int readInt () throws IOException {     return Integer.parseInt(next());     } } 
  
       
       

Lista de respuestas

5
 
vote
vote
La mejor respuesta
 

Buena implementación, ya es eficiente, pero como se indica en los comentarios se puede mejorar. Pocas sugerencias generales:

  • Formato El código : Muchos formato automático de soporte IDE o puede usar un formatter .

  • omitiendo los soportes no es una buena práctica : es mejor incluir los corchetes para evitar confusiones al leer o cambiar el código. Ver la diferencia de:

      static boolean isPrime(int n){        if(n==1)return false;        for (int i=2; i*i<=n; i++)            if (n%i==0) return false;       return true;  }    

    a:

      static boolean isPrime(int n) {     if (n == 1) {         return false;     }     for (int i = 2; i * i <= n; i++) {         if (n % i == 0) {             return false;         }     }     return true; }   
  • Organizar los métodos de general a específicos, es más fácil de seguir. De:

      static boolean isPrime(int n){  }  static int sum(int a, int b){      //call isPrime }   public static void main(String[] args)throws IOException{      // call readint     // call sum }   static String next () throws IOException { }  static int readInt () throws IOException {     // call next }   

    a:

      public static void main(String[] args)throws IOException{      // call readint     // call sum }  static int readInt () throws IOException {     // call next }   static String next () throws IOException { }  static int sum(int a, int b){      //call isPrime }   static boolean isPrime(int n){  }   
  • Los métodos readInt 998877665554433555544335 se puede reemplazar con java.util.Scanner :

      Scanner scanner = new Scanner(System.in); int q = scanner.nextInt();   
  • Cerrar los recursos : br.close()8 (o public static void main(String[] args)throws IOException{ // call readint // call sum } static int readInt () throws IOException { // call next } static String next () throws IOException { } static int sum(int a, int b){ //call isPrime } static boolean isPrime(int n){ } 9 ) Al final de static boolean isPrime(int n) { if (n == 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } 0 o si Se producen excepciones.

  • static boolean isPrime(int n) { if (n == 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } 1 no se usa.

  • El método static boolean isPrime(int n) { if (n == 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } 2 no suma dos enteros. Un mejor nombre puede ser static boolean isPrime(int n) { if (n == 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } 3

  • StringTokenizer se desaconseja para un nuevo código, desde los documentos:

    StringTokenizer es una clase heredada que se conserva para la compatibilidad razones aunque su uso se desalienta en el nuevo código. Es recomendado que cualquiera que busque esta funcionalidad use el método dividido de cadena o el paquete java.util.regex en su lugar.

Performance

Como se mencionó en los comentarios, ya que conoce el límite superior 10 ^ 5, puede precargar todos los números primeros con anticipación. El static boolean isPrime(int n) { if (n == 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } 4 lógico puede ser:

  1. Precomputa todos los números primeros hasta 10 ^ 5: Puede usar una matriz de Boolean inicializada con verdadero y luego configurar el índice correspondiente a FALSO si no es Prime. Por ejemplo:
  static boolean isPrime(int n) {     if (n == 1) {         return false;     }     for (int i = 2; i * i <= n; i++) {         if (n % i == 0) {             return false;         }     }     return true; } 5  

Código inspirado en aquí .

  1. analizar todas las preguntas del usuario
  2. Produce la suma de números primos para cada pregunta

Note : Dependiendo de cómo se calcula el tiempo total de funcionamiento, debe considerar el tiempo para analizar la entrada e imprimir los resultados. El tiempo total de funcionamiento también depende de la máquina donde ejecuta el programa.

 

Nice implementation, it's already efficient but as noted in the comments can be improved. Few general suggestions:

  • Format the code: many IDE support auto formatting or you can use an online formatter.

  • Omitting brackets is not good practice: it's better to include the brackets to avoid confusion when reading or changing the code. See the difference from:

    static boolean isPrime(int n){        if(n==1)return false;        for (int i=2; i*i<=n; i++)            if (n%i==0) return false;       return true;  }  

    To:

    static boolean isPrime(int n) {     if (n == 1) {         return false;     }     for (int i = 2; i * i <= n; i++) {         if (n % i == 0) {             return false;         }     }     return true; } 
  • Arrange the methods from general to specific, it's easier to follow. From:

    static boolean isPrime(int n){  }  static int sum(int a, int b){      //call isPrime }   public static void main(String[] args)throws IOException{      // call readint     // call sum }   static String next () throws IOException { }  static int readInt () throws IOException {     // call next } 

    To:

    public static void main(String[] args)throws IOException{      // call readint     // call sum }  static int readInt () throws IOException {     // call next }   static String next () throws IOException { }  static int sum(int a, int b){      //call isPrime }   static boolean isPrime(int n){  } 
  • The methods readInt and next can be replaced with java.util.Scanner:

    Scanner scanner = new Scanner(System.in); int q = scanner.nextInt(); 
  • Close the resources: br.close() (or scanner.close()) at the end of main or if exceptions occur.

  • PrintWriter pr is not used.

  • The method sum(int a, int b) does not sum two integers. A better name might be sumPrimesBetween

  • StringTokenizer is discouraged for new code, from the docs:

    StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.

Performance

As mentioned in the comments, since you know the upper bound 10^5 you can precompute all the prime numbers in advance. The main logic can be:

  1. Precompute all prime numbers until 10^5: you can use an array of boolean initialized to true and then set the corresponding index to false if not prime. For example:
static void computePrimesUntil(int n) {     isPrime = new boolean[n+1];     Arrays.fill(isPrime, true);     isPrime[0] = isPrime[1] = false;     for (int i = 2; i <= n; i++) {         if (isPrime[i] && (long) i * i <= n) {             for (int j = i * i; j <= n; j += i){                 isPrime[j] = false;             }         }     } } 

Code inspired from here.

  1. Parse all the questions from the user
  2. Output the sum of primes for each question

Note: depending on how the total running time is calculated, you need to consider the time to parse the input and print the results. The total running time also depends on the machine where you run the program.

 
 
         
         
1
 
vote

en esta respuesta , se le dice que puede precargar la lista de primos. Pero si el espacio no es una preocupación, podemos ir más allá y precalcular las sumas.

Suponiendo que tenemos una matriz static boolean isPrime(int n) { if (n == 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } 6 Dicha static boolean isPrime(int n) { if (n == 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } 7 nos dice si 99887766555443318 es primo o no.

  static boolean isPrime(int n) {     if (n == 1) {         return false;     }     for (int i = 2; i * i <= n; i++) {         if (n % i == 0) {             return false;         }     }     return true; } 9  

Ahora, si queremos saber la suma de números primos entre static boolean isPrime(int n){ } static int sum(int a, int b){ //call isPrime } public static void main(String[] args)throws IOException{ // call readint // call sum } static String next () throws IOException { } static int readInt () throws IOException { // call next } 0 y static boolean isPrime(int n){ } static int sum(int a, int b){ //call isPrime } public static void main(String[] args)throws IOException{ // call readint // call sum } static String next () throws IOException { } static int readInt () throws IOException { // call next } 1 Inclusive, podemos hacer un cálculo simple.

  static boolean isPrime(int n){  }  static int sum(int a, int b){      //call isPrime }   public static void main(String[] args)throws IOException{      // call readint     // call sum }   static String next () throws IOException { }  static int readInt () throws IOException {     // call next } 2  

Su algoritmo original fue $ mathcal {o} (qn ^ {1.5}) $ donde $ Q $ es el número de preguntas y $ n $ es el tamaño del rango. El formulario revisado en la otra respuesta es $ mathcal {o} (qn + n log log n) $ , que es algo mejor. Pero esta versión sería $ mathcal {o} (q + n log log n) $ . Tenga en cuenta que si $ q $ y $ n $ son iguales como en el peor de los casos de El problema, esto da poderes de 2.5, 2 y más de 1 pero menos de 2 respectivamente.

Tenga en cuenta que las preguntas reales pueden usar un rango más pequeño que $ n $ . Eso podría causar una falla de tiempo porque esta versión siempre suma el $ n $ . Podemos evitar esto leyendo todas las preguntas primero (usando más memoria nuevamente) y luego limitando nuestras sumas a los límites reales. En pseudocódigo, desde min (a) - 1 a max (b).

 

In this answer, you are told that you can precompute the list of primes. But if space is not a concern, we can go further and precalculate the sums.

Assuming we have an array prime such that prime[x] tells us if x is prime or not.

long[] primeSumUpTo = new long[prime.length];  // this explicit initialization is not necessary as 0 is the default value primeSumUpTo[0] = 0; for (int i = 1; i < prime.length; i++) {     primeSumUpTo[i] = primeSupUpTo[i - 1];     if (prime[i]) {         primeSumUpTo[i] += i;     } } 

Now if we want to know the sum of primes between a and b inclusive, we can just do a simple calculation.

long primeSumBetween = primeSumUpTo[b] - primeSumUpTo[a - 1]; 

Your original algorithm was \$\mathcal{O}(qn^{1.5})\$ where \$q\$ is the number of questions and \$n\$ is the size of the range. The revised form in the other answer is \$\mathcal{O}(qn + n \log \log n)\$, which is somewhat better. But this version would be \$\mathcal{O}(q + n \log \log n)\$. Note that if \$q\$ and \$n\$ are equal as in the worst case from the problem, this gives powers of 2.5, 2, and more than 1 but less than 2 respectively.

Note that the actual questions may use a smaller range than \$n\$. That could cause a timing fail because this version always sums the full \$n\$. We can avoid this by reading all the questions first (using more memory again) and then limiting our sums to the actual limits. In pseudocode, from min(a) - 1 to max(b).

 
 
 
 
0
 
vote

Guía de estilo

Lea una Guía de estilo . Deberías

  • Siempre use tirantes cuando use un bucle o si-declaraciones.
  • Agregar modificadores de acceso
  • Hacer espacios entre operadores.
  • No use * -imports.
  import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.util.StringTokenizer;  public class SumOfPrimes {     private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     private static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));     private static StringTokenizer st;      public static void main(String[] args) throws IOException {          int q = readInt();         for(int i = 0; i < q; i++) {             int a = readInt();             int b = readInt();              System.out.println(sum(a, b));         }     }       private static boolean isPrime(int n) {          if(n == 1) {             return false;          }         for (int i = 2; i * i <= n; i++) {             if (n % i == 0) {                 return false;             }         }         return true;      }         private static int sum(int a, int b) {          int sum = 0;          for(int i = b; i >= a; i--) {              boolean prime = isPrime(i);              if(prime) {                 sum += i;             }         }          return sum;      }       private static String next () throws IOException {         while (st == null || !st.hasMoreTokens()) {            st = new StringTokenizer(br.readLine().trim());         }         return st.nextToken();     }      static int readInt () throws IOException {         return Integer.parseInt(next());     } } 1  

Dile al usuario qué hacer

Cuando comencé el programa, no sabía qué hacer, porque el programa no me dijo:

  public static void main(String[] args) throws IOException {      System.out.println("How many calculations do you want to make?");     int q = readInt();     for(int i = 0; i < q; i++) {         System.out.println("Enter the lower bound:");         int a = readInt();         System.out.println("Enter the upper bound:");         int b = readInt();          System.out.println("Result:");         System.out.println(sum(a, b));     } }    

validación de entrada

El programa se bloquea cuando el usuario ingresa una cadena en lugar de un número. Puede evitar eso mediante el uso de una función como la siguiente en lugar de next() y readInt() :

  private static int getUserInput(String var) {     Scanner sc = new Scanner(System.in);     int number;     while(true) {         try {             System.out.print(var);             number = sc.nextInt();             if(number < 0) {                 throw new InputMismatchException();             }             return number;           }          catch(InputMismatchException e) {             System.out.println("Enter a number >= 0.");             sc.nextLine();         }     }  }   

Bound Bound & GT; Límite superior

Debe verificar si el usuario entra en a y b para que 9988776655544338 :

  public static void main(String[] args) throws IOException {      int q = getUserInput("How many calculations do you want to make?");     for(int i = 0; i < q; i++) {         int a = getUserInput("Enter the lower bound:");         int b = getUserInput("Enter the upper bound:");          if(a > b) {             int c = a;             a = b;             b = c;         }         System.out.println("Result:");         System.out.println(sum(a, b));     } }   

código

  import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.util.StringTokenizer;  public class SumOfPrimes {     private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     private static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));     private static StringTokenizer st;      public static void main(String[] args) throws IOException {          int q = readInt();         for(int i = 0; i < q; i++) {             int a = readInt();             int b = readInt();              System.out.println(sum(a, b));         }     }       private static boolean isPrime(int n) {          if(n == 1) {             return false;          }         for (int i = 2; i * i <= n; i++) {             if (n % i == 0) {                 return false;             }         }         return true;      }         private static int sum(int a, int b) {          int sum = 0;          for(int i = b; i >= a; i--) {              boolean prime = isPrime(i);              if(prime) {                 sum += i;             }         }          return sum;      }       private static String next () throws IOException {         while (st == null || !st.hasMoreTokens()) {            st = new StringTokenizer(br.readLine().trim());         }         return st.nextToken();     }      static int readInt () throws IOException {         return Integer.parseInt(next());     } } 0  
 

Style Guide

Please read a style guide. You should

  • always use braces when using a loop or if-statements.
  • add access modifiers
  • make spaces between operators.
  • Don't use *-imports.
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.util.StringTokenizer;  public class SumOfPrimes {     private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     private static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));     private static StringTokenizer st;      public static void main(String[] args) throws IOException {          int q = readInt();         for(int i = 0; i < q; i++) {             int a = readInt();             int b = readInt();              System.out.println(sum(a, b));         }     }       private static boolean isPrime(int n) {          if(n == 1) {             return false;          }         for (int i = 2; i * i <= n; i++) {             if (n % i == 0) {                 return false;             }         }         return true;      }         private static int sum(int a, int b) {          int sum = 0;          for(int i = b; i >= a; i--) {              boolean prime = isPrime(i);              if(prime) {                 sum += i;             }         }          return sum;      }       private static String next () throws IOException {         while (st == null || !st.hasMoreTokens()) {            st = new StringTokenizer(br.readLine().trim());         }         return st.nextToken();     }      static int readInt () throws IOException {         return Integer.parseInt(next());     } } 

Tell the user what to do

When I first started the program, I didn't know what to do, because the program didn't tell me:

public static void main(String[] args) throws IOException {      System.out.println("How many calculations do you want to make?");     int q = readInt();     for(int i = 0; i < q; i++) {         System.out.println("Enter the lower bound:");         int a = readInt();         System.out.println("Enter the upper bound:");         int b = readInt();          System.out.println("Result:");         System.out.println(sum(a, b));     } }  

Input validation

Your program crashes when the user enters a string instead of a number. You can avoid that by using a function like the following instead of next() and readInt():

private static int getUserInput(String var) {     Scanner sc = new Scanner(System.in);     int number;     while(true) {         try {             System.out.print(var);             number = sc.nextInt();             if(number < 0) {                 throw new InputMismatchException();             }             return number;           }          catch(InputMismatchException e) {             System.out.println("Enter a number >= 0.");             sc.nextLine();         }     }  } 

lower bound > upper bound

You should check if the user enters a and b so that a > b:

public static void main(String[] args) throws IOException {      int q = getUserInput("How many calculations do you want to make?");     for(int i = 0; i < q; i++) {         int a = getUserInput("Enter the lower bound:");         int b = getUserInput("Enter the upper bound:");          if(a > b) {             int c = a;             a = b;             b = c;         }         System.out.println("Result:");         System.out.println(sum(a, b));     } } 

Code

import java.util.Scanner; import java.io.IOException; import java.util.InputMismatchException;  public class SumOfPrimes {      public static void main(String[] args) {          int q = getUserInput("How many calculations do you want to make?");         for(int i = 0; i < q; i++) {             int a = getUserInput("Enter the lower bound:");             int b = getUserInput("Enter the upper bound:");              if(a > b) {                 int c = a;                 a = b;                 b = c;             }             System.out.println("Result:");             System.out.println(sum(a, b));         }     }       private static boolean isPrime(int n) {          if(n == 1) {             return false;          }         for (int i = 2; i * i <= n; i++) {             if (n % i == 0) {                 return false;             }         }         return true;      }         private static int sum(int a, int b) {          int sum = 0;          for(int i = b; i >= a; i--) {              boolean prime = isPrime(i);              if(prime) {                 sum += i;             }         }          return sum;      }      private static int getUserInput(String var) {         Scanner sc = new Scanner(System.in);         int number;         while(true) {             try {                 System.out.print(var);                 number = sc.nextInt();                 if(number < 0) {                     throw new InputMismatchException();                 }                 return number;               }              catch(InputMismatchException e) {                 System.out.println("Enter a number >= 0.");                 sc.nextLine();             }         }      } } 
 
 
       
       

Relacionados problema

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

8  Simple GCD Utility en Java  ( Simple gcd utility in java ) 
i anteriormente discutido El rendimiento se refiere a diferentes algoritmos GCD. Escribí una simple clase de Java que implementa el algoritmo binario GCD. E...

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...

2  Eliminación de un nodo en un árbol de búsqueda binario  ( Deletion of a node in a binary search tree ) 
Estoy buscando ver si mi implementación del método de eliminación / eliminación en un árbol de búsqueda binario es suficiente, legible y se ejecuta en un tiem...

5  Encuentre el próximo número Prime - Control de flujo de los bucles anidados 'para `  ( Find the next prime number flow control of nested for loops ) 
Este código funciona perfectamente, pero me molesta. Tener un bucle etiquetado y anidado Bucle, con un Enumerable<T>.Empty()0 Declaración, y un 9988777665...

2  Solucionador de rompecabezas de rascacielos en Java [cerrado]  ( Skyscraper puzzle solver in java ) 
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas. ¿Quieres ...

17  Implementación vectorial (física)  ( Vector physics implementation ) 
Recientemente comencé a aprender Java, y decidí implementar un sistema de vectores básico para otro sistema de partículas que estaba construyendo. join()9 ...

2  Fusionar la implementación de Sort Java  ( Merge sort java implementation ) 
¿Puede alguien revisar mi implementación de tipo de fusión en Java? ¿Es bueno / malo y puede mejorarse más? public class MyMergeSort { private int [] d...

5  Memoria / Performance of Merge Sort Code  ( Memory performance of merge sort code ) 
Escribí un código de tipo de combinación para un poco de bocadillo nocturno. Lo he puesto trabajando, pero solo estaba mirando a aprender si me faltaba algo e...

34  Clon a todo color del juego de la vida de Conway, con una GUI decente  ( Full color clone of conways game of life with a decent gui ) 
Escribí esto para aprender Javafx, y como excusa para volver a hacer el juego de la vida. Esta es la gui más compleja que he escrito, así que me gustaría come...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos