內容:

政治大學的諸君

軍情局攔截到了一系列由終極戰士(predator)所發出的密文。他們正密謀於某天的某一時刻大舉侵襲地球。若能及時破解攔截到的密碼,就能預防此災難的發生。很幸運的,終極戰士所使用的密碼並不終極。軍情局已發現了他們的密碼系統的規則。終極戰士是利用 Dirichlet 等差級數定理來產生某個質數,並利用此質數來加密訊息(明文)。

Dirichlet 級數定理是說,給定 a 與 d 兩個互質的正整數,則等差級數 a, a+d, a+2d, a+3d, a+4d, …, a+id, …中包含有無限多個質數。舉例來說,如果a=2, d=3, 則等差級數 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, … 中,包含無限多個質數 2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, …

只要知道其中某個質數,就可破解攔截到的密文。因此,諸君的任務就是,對於給定的 a, d, n,找到由 a, d 組成的等差級數中的質數集合中的第 n 個質數,並將結果回報給軍情局。舉例來說,2, 3, 5的結果為 23。2, 3, 8的結果為 47。

這是一個非常危險的任務。各位在任務期間產生的疲勞,頭暈目眩或混亂等等行為,皆源於終極戰士的電波干擾,但本局將採取一切不介入的原則。照往例,無論成功或失敗,軍情局都將會否認此任務的存在。此任務並將於 5 小時後自動失效。祝各位成功。

範例輸入:

1 1 1
253 50 85
307 24 79
331 221 177
269 58 102
367 186 151

範例輸出:

2
14503
5107
412717
25673
92809

==============================================

我改了一點點

d033: 2008 程式達人 G - 破解終極戰士(Predator)的密碼  

==============================================================menu

Created with colorer-take5 library. Type 'java'

import java.util.Scanner;


public class menu extends menuImplement{

    
    public static void main(String[] args) {
        Scanner scan =new Scanner(System.in);
        int a,d,n;//首項,公差,第n個質數
        try{
            while(1<2){
                System.out.println("請輸入要解密的Dirichlet 級數首項a,及公差d,及第n個質數 (a,d必須互質) 如要離開請輸入false:");
                
                    if(scan.hasNextBoolean()){
                        break;
                    }
                    a=scan.nextInt();
                    d=scan.nextInt();
                    n=scan.nextInt();
                    if(Coprime(a,d)){//如果a,n互質
                        if(Dirichlet(a,d,n)!=-1){//有找到
                            System.out.println("以"+a+"為首項"+d+"為公差的Dirichlet 級數內 第"+n+"個質數為:"+Dirichlet(a,d,n));
                            System.out.println();
                        }else{
                            System.out.println("雖然"+a+","+d+"有互質但沒有找到第"+n+"項質數");
                        }
                        
                    }else{//如果a,d沒有互質
                        System.out.println("a和d並沒有互質 請重新輸入");
                    }
            }
        }catch(Exception e){
            System.out.println("有輸入型別錯誤或不明錯誤 請檢查例外訊息:"+e);
        }
    }

}

 

==============================================================menuImplement

Created with colorer-take5 library. Type 'java'

import java.util.ArrayList;


public class menuImplement {
    protected static boolean  Coprime(int m,int n){//算互質
        int r;
        while(m != 0) { 
             r = n % m; 
             n = m; 
             m = r; 
             
        } 
        if(n==1){//互質
            return true;
        }else{//沒有互質
            return false;
        }
    }
    
    protected static int Dirichlet(int a,int d,int n){//算Dirichlet 級數的第n個質數
        ArrayList<Integer> Dirichlet=new ArrayList<Integer>();
        int count=0;
        int primeCount=0,an;
        while(1<2){
            an=a+count*d;
            if(Prime(an)){//an是質數
                primeCount++;
                if(primeCount==n){
                    break;
                }
            }
            count++;
        }
        
        if(primeCount==n){
            return an;
        }else{
            return -1;
        }
    }
    
    private static boolean Prime(int JudgeValue){//算是否為質數
        
        Boolean  WhetherPrime=true;
        if(JudgeValue==1){//1不是質數
            WhetherPrime=false;
            return WhetherPrime;
        }else
        if(JudgeValue%2==0&&JudgeValue!=2){//如果JudgeValue不是2又能被2整除,則不是質數傳回false
            WhetherPrime=false;
            return WhetherPrime;
        }else if(JudgeValue%3==0&&JudgeValue!=3){//如果JudgeValue不是3又能被3整除,則不是質數傳回false
            WhetherPrime=false;
            return WhetherPrime;
        }else if(JudgeValue%5==0&&JudgeValue!=5){//如果JudgeValue不是5又能被5整除,則不是質數傳回false
            WhetherPrime=false;
            return WhetherPrime;
        }else if(JudgeValue%7==0&&JudgeValue!=7){//如果JudgeValue不是7又能被7整除,則不是質數傳回false
            WhetherPrime=false;
            return WhetherPrime;
        }else{//不是以上情況從11到JudgeValue開根號 去除JudgeValue 可整除不是質數
            for(int i=11;i<=(int)Math.ceil(Math.sqrt(JudgeValue));i+=2){
              if(JudgeValue%i==0){
                WhetherPrime=false;
                return WhetherPrime;
              }
            }
       }
        return WhetherPrime;//以上情況都不能整除則是質數 傳回預設值true
    }
}

, , , ,
創作者介紹

Mazs's Notes

cookiesp 發表在 痞客邦 PIXNET 留言(0) 人氣()