Java中的Euler项目“最大素因子”(#3)

Question

13195的素因子为5、7、13和29。数字600851475143中最大的素因子是什么？

我在一些Java 8的帮助下编写了以下代码，我将在代码中解释与Java 7等价的内容。我想要一般性的评论。我要放弃的一点是，我写的程序没有给出最大的素因子，而是给出了所有的素因子。

public class ProjectEuler {
    private final static int WARMUP_COUNT = 0;
    private final static int REAL_COUNT = 1;

    private final List<Problem<?>> problems = new ArrayList<>();

    private void init() {
        problems.add(new Problem1());
        problems.add(new Problem2());
        problems.add(new Problem3(600851475143L));

        process();
    }

    private void process() {
        problems.stream().forEachOrdered(new ProblemConsumer());
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        new ProjectEuler().init();
    }

    private class ProblemConsumer implements Consumer<Problem<?>> {
        @Override
        public void accept(Problem<?> problem) {            
            for (int i = 0; i < WARMUP_COUNT; i++) {
                problem.run();
            }
            System.gc();

            long start = System.nanoTime();
            for (int i = 0; i < REAL_COUNT; i++) {
                problem.run();
            }
            double average = (System.nanoTime() - start) * 1.0d / REAL_COUNT;

            String result = problem.getResult();

            System.out.println(problem.getName() + ": " + result + " (" + String.format("%.5f", (average / 1_000_000.0)) + " ms" + ")");
        }        
    }
}

public class Problem3 extends Problem<List<Long>> {
    private final long number;

    public Problem3(final long number) {
        this.number = number;
    }

    @Override
    public void run() {
        long numberCopy = number;
        result = new ArrayList<>();
        while (numberCopy > 1) {
            PrimeGenerator primeGenerator = new PrimeGenerator();
            while (primeGenerator.hasNext()) {
                long prime = primeGenerator.nextLong();
                if (numberCopy % prime == 0) {
                    result.add(prime);
                    numberCopy /= prime;
                    break;
                }
            }
        }
    }

    @Override
    public String getName() {
        return "Problem 3";
    }
}

public class PrimeGenerator implements PrimitiveIterator.OfLong {
    private final static LongNode HEAD_NODE = new LongNode(2);

    private LongNode lastNode = HEAD_NODE;
    private long current = 2;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public long nextLong() {
        if (lastNode.value == current) {
            if (lastNode.next != null) {
                long old = lastNode.value;
                lastNode = lastNode.next;
                current = lastNode.value;
                return old;
            }
            return current++;
        }
        while (true) {
            if (isPrime(current)) {
                appendNode(current);
                return current++;
            }
            current++;
        }
    }

    private boolean isPrime(final long number) {        
        LongNode prime = HEAD_NODE;
        while (prime != null && prime.value <= number) {
            if (number % prime.value == 0) {
                return false;
            }
            prime = prime.next;
        }
        return true;
    }

    private void appendNode(final long value) {
        LongNode newNode = new LongNode(value);
        couple(lastNode, newNode);
        lastNode = newNode;
    }

    private void couple(final LongNode first, final LongNode second) {
        first.next = second;
        second.previous = first;
    } 

    private static class LongNode {
        public final long value;

        public LongNode previous;
        public LongNode next;

        public LongNode(final long value) {
            this.value = value;
        }
    }

    public static LongStream infiniteStream() {
        return StreamSupport.longStream(
                Spliterators.spliteratorUnknownSize(new PrimeGenerator(), Spliterator.ORDERED | Spliterator.IMMUTABLE), false
        );
    }
}

Java 8备注：

• 我没有在这个答案中使用PrimeGenerator.infiniteStream()，所以没有必要考虑它。
• ProjectEuler类只是为了方便而提供的。
• PrimiteIterator.OfLong是Java7等效的Iterator<Long>的原始包装器。

我在这个练习中用到的想法是，我需要一个素数的列表。每一次，当素数模是零时，我会在列表中添加一个因子，除以这个素数。

关于速度的其他评论，我认为很有趣，我还运行了代码，总结了第一个百万素数。

• 当适当的基准测试，10000翘曲和10000实际测试时，时间平均为7.5ms。
• 然而，只有一个真正的测试，它仍然运行了一个相当长的时间，至少一个小时，我认为。

Answer 1

实际上，您的迭代器是两个迭代器-一个用于已知素数(来自先前的“翘曲”)，另一个用于未知素数。已知的主要迭代器的实现选择看起来有点麻烦--您可以使用一个简单的Long列表，然后遍历它：

private final static List<Long> KNOWN_PRIMES = new LinkedList<Long>();

private Iterator<Long> knownPrimeIterator = KNOWN_PRIMES.iterator();
private long lastResult = 1;

public long nextLong() {
    if (knownPrimeIterator != null && knownPrimeIterator.hasNext()) {
        lastResult = knownPrimeIterator.next().toLong();
    } else {
        knownPrimeIterator = null;
        lastResult = findNextPrime(lastResult+1);
        KNOWN_PRIMES.add(new Long(lastResult));
    }
    return lastResult;
}

private long findNextPrime(long startFrom) {
    // whatever here...
}

关于你的基准，我认为“热身”有点像作弊.您正在将结果缓存在静态数组中。如果您想要一个高性能的解决方案，您可以预先计算出第一个1,000,000素数，将它们保存到一个文件中，然后在过程开始时读取它们.:P

Answer 2

几点意见：

• 我同意不需要使用LinkedList的自定义实现是一种糟糕的做法。
• 公共可变字段是不好的。
• 在争论中加上最后一句被认为是迂腐的。
• 我不喜欢你生成素数的方法。通过迭代所有较小的素数来检查一个数字是否是素数。两个可能的改进是只在范围1，\sqrt{x}中的素数上迭代，或者使用像Miller-Rabin这样的花哨的素数测试。但是一种更快更容易的方法是使用伊拉托斯提尼来生成素数。