andy6804tw
3/27/2017 - 5:18 PM

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4519 這題是2016/12/10CPE第四題，並不難主要是要先建立質數表才不會LT

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4519

這題是2016/12/10CPE第四題，並不難主要是要先建立質數表才不會LTE 至於怎麼快速建表呢?簡單來說質數一定是奇數，不多說下面有質數建表範例 這題主要是找尋該數在質數的Gap當中有幾個非質數數目，若本身為質數就輸出零

Q1644: Prime Gap.java
content_copyfile_download
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		ArrayList<Integer> primeTable = new ArrayList<Integer>();
        primeTable.add(2);
        for(int i = 3;i<=1299709 ; i += 2)
        {
            boolean check = true;
            for(int j = 3; j * j <= i; j += 2)
            {
                if(i % j == 0)
                {
                    check=false;
                    break;
                }
            }
            if(check)
                primeTable.add(i);
        }
      while(true){
    	   int num=scn.nextInt(),i;
    	   Boolean b=true;
    	   if(num==0)
    		   break;
    	   for(i=0;i<primeTable.size();i++){
    		   if(primeTable.get(i)==num){
    			   b=false;
    			   break;
    		   }
    		   else if(primeTable.get(i)>num){
    			   break;
    		   }
    	   }
    	   if(b){
    		   int count=0;
    		   for(int j=primeTable.get(i-1);j<primeTable.get(i);j++)
    			   count++;
    		   System.out.println(count);
    	   }else{
    		   System.out.println("0");
    	   }
       }
	}
	/*題目：Q1644: Prime Gap
    作者：1010
    時間：西元 2017 年 3 月 */
}
PrimeTable.java
content_copyfile_download
/* package whatever; // don't place package name! */

import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        ArrayList<Integer> primeTable = new ArrayList<Integer>();
        primeTable.add(2);
        for(int i = 3;i<1000000 ; i += 2)
        {
            boolean check = true;
            for(int j = 3; j * j <= i; j += 2)
            {
                if(i % j == 0)
                {
                    check=false;
                    break;
                }
            }
            if(check)
                primeTable.add(i);
        }
        for(int i = 0; i < primeTable.size(); ++i)
            System.out.println(primeTable.get(i));
    }
    /*題目：PrimeTable質數建表
    作者：1010
    時間：西元 2017 年 3 月 */
}