發表新討論
#6098: java 過不了


s11113151 (飛走跑跳動)

學校 : 樹德科技大學
編號 : 20657
來源 : [118.163.247.69]
最後登入時間 ：
2019-11-28 10:12:42
d709. 判断质数（一） -- 判断质数系列 | From: [114.27.157.252] | 發表日期 : 2011-11-20 15:39

java 沒辦法通過這測資= =

我已經把 i 跳奇數 過偶數 跑根號了 還是TLE .. 

 
#6099: Re:java 過不了


s111110111 (山口)

學校 : 國立臺灣師範大學
編號 : 21172
來源 : [220.137.25.144]
最後登入時間 ：
2014-09-13 18:54:39
d709. 判断质数（一） -- 判断质数系列 | From: [111.250.57.178] | 發表日期 : 2011-11-21 00:06

java 沒辦法通過這測資= =

我已經把 i 跳奇數 過偶數 跑根號了 還是TLE .. 

同意！建表也過不了

在三秒內無法到達 line 14

除非把建表以外的程式碼全部拿掉.... 

  1. import java.util.Scanner;  
  2.   
  3. public class D709 {  
  4.     public static void main(String[] args) {  
  5.         Scanner scanner = new Scanner(System.in);  
  6.   
  7.         boolean isPrime[] = new boolean[1000001];  
  8.   
  9.         isPrime[1] = true;  
  10.         for(int i = 3; i <= isPrime.length; i += 2)  
  11.             if(isPrime[i] == false)  
  12.                 for(int j = i+i; j <= isPrime.length; j += i)  
  13.                     isPrime[j] = true;  
  14.   
  15.         while(scanner.hasNext()) {  
  16.             int n = scanner.nextInt();  
  17.   
  18.             if(n == 0)  
  19.                 break;  
  20.   
  21.             if(n == 2)  
  22.                 System.out.println(0);  
  23.             else if(n%2 == 0)  
  24.                 System.out.println(1);  
  25.             else  
  26.                 System.out.println(!isPrime[n]?0:1);  
  27.         }  
  28.     }  
  29. }  

還是有更有效率的演算法呢

跪求 Orz

 
#6100: Re:java 過不了


s11113151 (飛走跑跳動)

學校 : 樹德科技大學
編號 : 20657
來源 : [118.163.247.69]
最後登入時間 ：
2019-11-28 10:12:42
d709. 判断质数（一） -- 判断质数系列 | From: [114.27.157.252] | 發表日期 : 2011-11-21 00:13

java 沒辦法通過這測資= =

我已經把 i 跳奇數 過偶數 跑根號了 還是TLE .. 

同意！建表也過不了

在三秒內無法到達 line 14

除非把建表以外的程式碼全部拿掉.... 

  1. import java.util.Scanner;  
  2.   
  3. public class D709 {  
  4.     public static void main(String[] args) {  
  5.         Scanner scanner = new Scanner(System.in);  
  6.   
  7.         boolean isPrime[] = new boolean[1000001];  
  8.   
  9.         isPrime[1] = true;  
  10.         for(int i = 3; i <= isPrime.length; i += 2)  
  11.             if(isPrime[i] == false)  
  12.                 for(int j = i+i; j <= isPrime.length; j += i)  
  13.                     isPrime[j] = true;  
  14.   
  15.         while(scanner.hasNext()) {  
  16.             int n = scanner.nextInt();  
  17.   
  18.             if(n == 0)  
  19.                 break;  
  20.   
  21.             if(n == 2)  
  22.                 System.out.println(0);  
  23.             else if(n%2 == 0)  
  24.                 System.out.println(1);  
  25.             else  
  26.                 System.out.println(!isPrime[n]?0:1);  
  27.         }  
  28.     }  
  29. }  

還是有更有效率的演算法呢

跪求 Orz

我的code ...

/**********************************************************************************/

/*  Problem: d709 "判断质数（一）" from 判断质数系列                 */

/*  Language: JAVA (1074 Bytes)                                                   */

/*  Result: TLE(3s) judge by this@ZeroJudge                                       */

/*  Author: s11113151 at 2011-11-20 15:35:03                                      */

/**********************************************************************************/

 

 

import java.io.*;

 

public class test {

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

    BufferedReader buf = new BufferedReader ( 

new InputStreamReader(System.in));

String s;

while ( ( s = buf.readLine() ) != null ) {  

 int a = Integer.parseInt(s);  

 if ( a == 0 ) break;

 boolean sure = true;

 sure = a == 1 ? false : sure ;

 sure = a % 2 == 0 && a != 2 ? false : sure;

 sure = a % 3 == 0 && a != 3  ? false : sure;

 sure = a % 5 == 0 && a != 5  ? false : sure;

 sure = a % 7 == 0 && a != 7  ? false : sure;

 int b = (int)Math.sqrt(a) , i = 7;

 while ( i <= b && sure) {

   if ( a % i == 0  ) sure =  false ;

i+=4;

if ( a % i == 0  ) sure =  false ;

i+=2;

if ( a % i == 0  ) sure =  false ;

i+=4;

if ( a % i == 0  ) sure =  false ;

i+=2;

if ( a % i == 0  ) sure =  false ;

i+=4;

if ( a % i == 0  ) sure =  false ;

i+=6;

if ( a % i == 0  ) sure =  false ;

i+=2;

if ( a % i == 0  ) sure =  false ;

i+=6;

 }

 System.out.print(sure ? "0" : "1");

 System.out.print("\\n");

}

  }

}

 

因為初學java 所以都是一些簡單的技巧

 我迴圈是用質數去跑 還是TLE= =! 

 
ZeroJudge Forum