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

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

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

问题

import java.io.*;
import java.util.*;

class TestClass {
    public static long prime(long l, long r) {
        boolean flag = false;
        long count = 0;
        long i, j;
        for (i = l; i <= r; i++) {
            flag = false;
            if (i >= 2) {
                for (j = 2; j < i; j++) {
                    if (i % j == 0) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    count += i;
                }
            }
        }
        return count;
    }

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int i = 0;
        int x = t;
        long res[] = new long[t];
        while (t > 0) {
            StringTokenizer s = new StringTokenizer(br.readLine());
            long l = Long.parseLong(s.nextToken());
            long r = Long.parseLong(s.nextToken());
            res[i] = prime(l, r);
            t--;
            i++;
        }
        for (i = 0; i < x; i++) {
            System.out.println(res[i]);
        }
    }
}
英文:

`

  import java.io.*;
import java.util.*;
class TestClass {
public static long prime(long l,long r){
boolean flag=false;
long count=0;
long i,j;
for(i=l;i&lt;=r;i++){
flag=false;
if(i&gt;=2){
for(j=2;j&lt;i;j++){
if(i%j==0){
flag=true;
break;
}
}
if(flag==false){
count+=i;
}
}
}
return count;
}
public static void main(String args[] ) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
int i=0;
int x=t;
long res[]=new long[t];
while(t&gt;0){
StringTokenizer s=new StringTokenizer(br.readLine());
long l=Long.parseLong(s.nextToken());
long r=Long.parseLong(s.nextToken());
res[i]=prime(l,r);
t--;
i++;
}
for(i=0;i&lt;x;i++){
System.out.println(res[i]);
}

`

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):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class TestClass {

    public static long sumPrime(long l, long r) {
        long count = 0;
        for (long n = l; n <= r; n++) {
            if (isPrime(n)) count += n;
        }
        return count;
    }

    public static boolean isPrime(long n) {
        if (n < 2) return false;
        if (n == 2) return true;
        for (long i = 2; i <= (long) Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Loop: ");
        int t = Integer.parseInt(br.readLine());
        long[] res = new long[t];
        for (int i = 0; i < t; i++) {
            System.out.print("(l-r)?: ");
            String[] s = br.readLine().split(" ");
            long l = Long.parseLong(s[0]);
            long r = Long.parseLong(s[1]);
            res[i] = sumPrime(l, r);
        }
        System.out.print("Result: ");
        for (int i = 0; i < t; i++) {
            System.out.printf("%d  ", res[i]);
        }
    }
}
英文:

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class TestClass {
public static long sumPrime(long l, long r) {
long count = 0;
for (long n = l; n &lt;= r; n++) {
if (isPrime(n)) count += n;
}
return count;
}
public static boolean isPrime(long n) {
if (n &lt; 2) return false;
if (n == 2) return true;
for (long i = 2; i &lt;= (long) Math.sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print(&quot;Loop: &quot;);
int t = Integer.parseInt(br.readLine());
long[] res = new long[t];
for (int i = 0; i &lt; t; i++) {
System.out.print(&quot;(l-r)?: &quot;);
String[] s = br.readLine().split(&quot; &quot;);
long l = Long.parseLong(s[0]);
long r = Long.parseLong(s[1]);
res[i] = sumPrime(l, r);
}
System.out.print(&quot;Result: &quot;);
for (int i = 0; i &lt; t; i++) {
System.out.printf(&quot;%d  &quot;, res[i]);
}
}
}

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

发表评论

匿名网友

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

确定