Iam getting a TLE for a code to print sum of all primes between given 2 numbers(inclusive) in java

huangapple
go评论130阅读模式
英文:

Iam getting a TLE for a code to print sum of all primes between given 2 numbers(inclusive) in java

问题

  1. import java.io.*;
  2. import java.util.*;
  4. class TestClass {
  5.     public static long prime(long l, long r) {
  6.         boolean flag = false;
  7.         long count = 0;
  8.         long i, j;
  9.         for (i = l; i <= r; i++) {
  10.             flag = false;
  11.             if (i >= 2) {
  12.                 for (j = 2; j < i; j++) {
  13.                     if (i % j == 0) {
  14.                         flag = true;
  15.                         break;
  16.                     }
  17.                 }
  18.                 if (!flag) {
  19.                     count += i;
  20.                 }
  21.             }
  22.         }
  23.         return count;
  24.     }
  26.     public static void main(String args[]) throws IOException {
  28.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  29.         int t = Integer.parseInt(br.readLine());
  30.         int i = 0;
  31.         int x = t;
  32.         long res[] = new long[t];
  33.         while (t > 0) {
  34.             StringTokenizer s = new StringTokenizer(br.readLine());
  35.             long l = Long.parseLong(s.nextToken());
  36.             long r = Long.parseLong(s.nextToken());
  37.             res[i] = prime(l, r);
  38.             t--;
  39.             i++;
  40.         }
  41.         for (i = 0; i < x; i++) {
  42.             System.out.println(res[i]);
  43.         }
  44.     }
  45. }
英文:

`

  1.   import java.io.*;
  2. import java.util.*;
  3. class TestClass {
  4. public static long prime(long l,long r){
  5. boolean flag=false;
  6. long count=0;
  7. long i,j;
  8. for(i=l;i&lt;=r;i++){
  9. flag=false;
  10. if(i&gt;=2){
  11. for(j=2;j&lt;i;j++){
  12. if(i%j==0){
  13. flag=true;
  14. break;
  15. }
  16. }
  17. if(flag==false){
  18. count+=i;
  19. }
  20. }
  21. }
  22. return count;
  23. }
  24. public static void main(String args[] ) throws IOException {
  25. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  26. int t=Integer.parseInt(br.readLine());
  27. int i=0;
  28. int x=t;
  29. long res[]=new long[t];
  30. while(t&gt;0){
  31. StringTokenizer s=new StringTokenizer(br.readLine());
  32. long l=Long.parseLong(s.nextToken());
  33. long r=Long.parseLong(s.nextToken());
  34. res[i]=prime(l,r);
  35. t--;
  36. i++;
  37. }
  38. for(i=0;i&lt;x;i++){
  39. System.out.println(res[i]);
  40. }

`

I don't know what is the reason for TLE for my code. How can I optimize my code inorder to get rid of that error? Can anyone help me to find the optimal solution for my code.
Thank you in advance.

答案1

得分: 1

将您的代码分割，消除不必要的变量。对于素数，只需重复到sqrt (n)：

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  5. class TestClass {
  7.     public static long sumPrime(long l, long r) {
  8.         long count = 0;
  9.         for (long n = l; n <= r; n++) {
  10.             if (isPrime(n)) count += n;
  11.         }
  12.         return count;
  13.     }
  15.     public static boolean isPrime(long n) {
  16.         if (n < 2) return false;
  17.         if (n == 2) return true;
  18.         for (long i = 2; i <= (long) Math.sqrt(n); i++) {
  19.             if (n % i == 0) return false;
  20.         }
  21.         return true;
  22.     }
  24.     public static void main(String[] args) throws IOException {
  25.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  26.         System.out.print("Loop: ");
  27.         int t = Integer.parseInt(br.readLine());
  28.         long[] res = new long[t];
  29.         for (int i = 0; i < t; i++) {
  30.             System.out.print("(l-r)?: ");
  31.             String[] s = br.readLine().split(" ");
  32.             long l = Long.parseLong(s[0]);
  33.             long r = Long.parseLong(s[1]);
  34.             res[i] = sumPrime(l, r);
  35.         }
  36.         System.out.print("Result: ");
  37.         for (int i = 0; i < t; i++) {
  38.             System.out.printf("%d  ", res[i]);
  39.         }
  40.     }
  41. }
英文:

Split your code, eliminate unnecessary variables. For prime numbers, just repeat up to sqrt (n):

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. class TestClass {
  5. public static long sumPrime(long l, long r) {
  6. long count = 0;
  7. for (long n = l; n &lt;= r; n++) {
  8. if (isPrime(n)) count += n;
  9. }
  10. return count;
  11. }
  12. public static boolean isPrime(long n) {
  13. if (n &lt; 2) return false;
  14. if (n == 2) return true;
  15. for (long i = 2; i &lt;= (long) Math.sqrt(n); i++) {
  16. if (n % i == 0) return false;
  17. }
  18. return true;
  19. }
  20. public static void main(String[] args) throws IOException {
  21. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  22. System.out.print(&quot;Loop: &quot;);
  23. int t = Integer.parseInt(br.readLine());
  24. long[] res = new long[t];
  25. for (int i = 0; i &lt; t; i++) {
  26. System.out.print(&quot;(l-r)?: &quot;);
  27. String[] s = br.readLine().split(&quot; &quot;);
  28. long l = Long.parseLong(s[0]);
  29. long r = Long.parseLong(s[1]);
  30. res[i] = sumPrime(l, r);
  31. }
  32. System.out.print(&quot;Result: &quot;);
  33. for (int i = 0; i &lt; t; i++) {
  34. System.out.printf(&quot;%d  &quot;, res[i]);
  35. }
  36. }
  37. }

huangapple
  • 本文由 发表于 2020年7月22日 10:22:06
  • 转载请务必保留本文链接：https://go.coder-hub.com/63025826.html
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定