白駿1978号は少数を探しています

1420 ワード
algorithm Java テキストリンク
与えられたN個の数値では、小数を分解するアルゴリズムを作成する必要があります.
小数は1と自分だけの数字なので、簡単に言えば、数ごとに2から自分まで解決できる問題です.しかし,時間的複雑度はO(N)であり,効率は低下した.
public class Main{
    public static boolean isPrime(int num){
        if(num == 1) return false;
        for(int i=2; i<num; i++){
            if(num%i==0) return false;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        int ans = 0;
        for(int i=0; i<t; i++){
            int a = sc.nextInt();
            if(isPrime(a)) ans++;
        }
        System.out.println(ans);
    }
}
異なる案を取らなければならない.
これは平方根を利用する方法です.
判別が必要なNがA X Bの合成数であると仮定すると、1≦A,BA、B>sqrt(N).
最終的には、AまたはBはsqrt(N)以下でなければならない.
2から自分で点を照らし合わせるより、与えられた数の平方根だけに分けたほうが効率的です.
public class Main{
    public static boolean isPrime(int num){
        if(num == 1) return false;
        for(int i=2; i<=Math.sqrt(num); i++){
            if(num%i==0) return false;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        int ans = 0;
        for(int i=0; i<t; i++){
            int a = sc.nextInt();
            if(isPrime(a)) ans++;
        }
        System.out.println(ans);
    }
}
Python用のvscodeの設定方法(テスト,カバレッジ,プロファイリング)
Util:アマゾンCloudWatch警報をテストすること