Java分段筛代码运行缓慢，未达预期时间复杂度性能

Hey there! Let's break down why your segmented sieve is running slow and fix it up with practical optimizations—these changes should get it running at the expected time complexity.

Common Bottlenecks & Fixes #

1. Replace ArrayList<Integer> nonPrimes with a boolean array

Using an ArrayList to track non-primes is a huge performance hit. Every add() operation involves potential array resizing and object overhead, which is totally unnecessary when we just need a true/false flag for each number in the range.

Instead, use a compact boolean array where isComposite[i] marks whether start + i is a composite number. This cuts down on memory usage and makes access/updates nearly instantaneous.

2. Optimize the starting point for marking multiples

Right now, you might be marking multiples starting from too low a value, which wastes cycles. For each prime p:

• Calculate the first multiple of p that falls within your range using ((start + p - 1) / p) * p (this rounds up to the nearest multiple of p).
• Skip any multiples smaller than p*p—these would have already been marked by smaller primes in your initial primes list.
• Also, break early if p*p exceeds last—any number larger than that in the range can't be composite (since its factors would have already been checked).

Don't forget to use long for calculations here to avoid integer overflow when dealing with large primes or ranges.

3. Cut down on unnecessary I/O

That System.out.println() call in your worker thread might seem harmless, but if you're running multiple threads, synchronized console output creates a bottleneck. Either remove it entirely for performance testing, or switch to a lightweight logging framework with debug-level logging that you can disable in production.

4. Handle edge cases cleanly

If your start value is 1, make sure to mark it as composite immediately—1 isn't a prime, and leaving it unmarked will skew your results.

Optimized Code Example #

Here's how your revised sieveWorker might look with these fixes:

public ArrayList<Integer> sieveWorker(int start, int last, ArrayList<Integer> primes) {
    int rangeSize = last - start + 1;
    boolean[] isComposite = new boolean[rangeSize];

    // Mark 1 as composite if it's in the range
    if (start == 1) {
        isComposite[0] = true;
    }

    for (int p : primes) {
        long pSquared = (long) p * p;
        // Stop early if prime squared exceeds the end of the range
        if (pSquared > last) {
            break;
        }

        // Find the first multiple of p within [start, last]
        long firstMultiple = ((start + p - 1) / p) * p;
        // Start marking from p*p (smaller multiples already handled)
        firstMultiple = Math.max(firstMultiple, pSquared);

        // Mark all multiples of p in the range
        for (long i = firstMultiple; i <= last; i += p) {
            isComposite[(int) (i - start)] = true;
        }
    }

    // Collect all unmarked (prime) numbers in the range
    ArrayList<Integer> primesInRange = new ArrayList<>();
    for (int i = 0; i < rangeSize; i++) {
        if (!isComposite[i]) {
            primesInRange.add(start + i);
        }
    }

    return primesInRange;
}

Bonus: Optimize your initial primes list #

Make sure the primes list you're passing in is generated efficiently using a standard Sieve of Eratosthenes up to sqrt(last). Using a boolean array for that initial sieve will also keep things fast and memory-efficient.

These changes should eliminate most of the slowdown and get your segmented sieve running at its intended O(n log log n) time complexity.

内容的提问来源于stack exchange，提问作者CB95