java - 质因数分解解密

Question

我有一个程序，应该将一个数字解密为素数。素数也有顺序:例如，2 是第一个素数，3 是第二个素数，5 是第三个素数，依此类推。索引为 1 代表 a，2 代表 b，3 代表 c，依此类推。我不知道如何比较两个数组列表以便为每个素数分配索引，以便我可以解码数字 72216017 中加密的单词。数字 72216017 的素数为 17,19,47,67,71 。如果2,3,5,7,11...是a,b,c,d,e...这五个素数组成了ghost这个词，我只是不知道如何对这些数字进行分配和排序他们的索引。

package name;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class PrimeFactorsEffective {
    private static int z;
    private int w = z;

    public static List<Integer> primeFactors(int numbers) {
        int n = numbers;
        List<Integer> factors = new ArrayList<Integer>();
        for (int i = 2; i <= n / i; i++) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
            if (n > 1) {
                factors.add(n);
                System.out.println(factors);
                z = Collections.max(factors);
            }
        }
        return factors;
    }

    public static void main(String[] args) {
        System.out.println("Primefactors of 72216017");
        for (Integer integer : primeFactors(72216017)) {
            System.out.println(integer);
        }
        List<Integer> factors1 = new ArrayList<Integer>();
        List<String> index1 = new ArrayList<String>();
        int i;
        int element = 0;
        int num = 0;
        int maxCheck = z; // maxCheck limit till which you want to find prime numbers
        boolean isPrime = true;
        String primeNumbersFound = "";


        //Start loop 1 to maxCheck
        for (i = 1; i <= maxCheck; i++) {
            isPrime = CheckPrime(i);
            if (isPrime) {
                primeNumbersFound = primeNumbersFound + i + " ";
                factors1.add(i);
                factors1.get(num);
            }
        }
        System.out.println("Prime numbers from 1 to " + maxCheck + " are:");
        System.out.println(factors1);
    }

    public static boolean CheckPrime(int numberToCheck) {
        int remainder;
        for (int i = 2; i <= numberToCheck / 2; i++) {
            remainder = numberToCheck % i;
            if (remainder == 0) {
                return false;
            }
        }
        return true;
    }
}

Answer 1

您可以将素数存储在 List 中(此列表中的素数将按递增顺序排列)。现在您可以使用Collections.BinarySearch获取要查找对应字母表的素数的索引。一旦你得到了索引(根据你这里的索引从1开始，所以 a 的索引是1， b 的索引是2， c 的索引是3等等)你可以简单地做类似 char currentCharacter = (char) ('a' + primeIndex - 1)和变量 currentCharacter将存储对应于 primeIndex 的字母表.

我想建议的其他一些小事情:

1. 要检查一个数是否为素数，您可以简单地检查numberToCheck的平方根。 。所以你可以替换你的循环 for (int i = 2; i <= numberToCheck / 2; i++)至for (int i = 2; i*i <= numberToCheck; i++) 。请注意，使用 Math.sqrt 计算平方根不是一个好主意。 ，您可以使用类似 i*i <= numberToCheck 的条件.
2. 请不要为您的包裹命名看似随意的名称。
3. 从 Java SE 7 开始，初始化列表时不需要显式类型参数。您可以替换List<Integer> factors1 = new ArrayList<Integer>()与 List<Integer> factors1 = new ArrayList<>() 。请阅读this了解更多信息。
4. 你的因子方法对我来说看起来不太好，它不能给出正确的结果。请参阅以下给出正确结果的方法:

{{

public static List<Integer> primeFactors(int numbers) {
    int n = numbers;
    List<Integer> factors = new ArrayList<>();
    for (int i = 2; n>1; i++) {
        while (n % i == 0) {
            factors.add(i);
            n /= i;
        }
    }
    z = Collections.max(factors);
    return factors;
}