#Bitsieve working incorrectly

1 messages · Page 1 of 1 (latest)

eager plaza
#

Hi everyone,
For a challenge, I wrote (or smashed together) a segmented sieve which works fine, then I tried to implement a bitsieving component, and now it stops returning the correct number past somewhere to the 20th prime number.

Here's the code -- I'm completely stumpted. Any help is deeply appreciated.

surreal havenBOT
#

<@&987246399047479336> please have a look, thanks.

#

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

#

g the correct results. I'm not sure what went wrong, but I would appreciate any help in figuring out the issue.

Here is my code for the bitsieve component:

import math

def bitsieve(n):
    size = (n - 1) // 2
    prime = [True] * size
    limit = int(math.sqrt(n)) + 1

    for i in range(1, limit):
        if prime[i]:
            p = i * 2 + 1
            for j in range(i * i * 2 + 6 * i + 3, size, p):
                prime[j] = False

    return [2] + [i * 2 + 1 for i, val in enumerate(prime) if val]

# Testing the bitsieve component
print(bitsieve(100))

The expected output should be a list of prime numbers up to 100, but instead, it gives incorrect results.

Any suggestions or insights would be greatly appreciated. Thank you!

eager plaza
# 
public static int primeFinderOptimized(int num) {
        int l1CacheSize = 32768;
        int primes = (formula goes here)
        int sqrt = (int) Math.sqrt(primes);
        int sieveSize = 64*Math.max(sqrt, l1CacheSize);
        int count = (primes < 2) ? 0 : 1;
        ArrayList<Integer> primeList = new ArrayList<>();
        ArrayList<Integer> multipleList = new ArrayList<>();
        /*boolean[] sieve = new boolean[sieveSize];
        boolean[] isPrime = new boolean[sqrt+1];*/
        int[] sieve = new int[sieveSize/64];
        int[] isPrime = new int[(sqrt/64)+1];
        int i = 3;
        int k = 3;
        int p = 3;
        for (int lowLimit = 0; lowLimit <= primes; lowLimit += sieveSize) {
            int highLimit = Math.min(lowLimit + sieveSize - 1, primes);
            Arrays.fill(sieve, 0);

            for (; i*i <= highLimit; i+=2) {
                if (ifnotPrime(isPrime, i) == 0) {
                    for (int j = i*i; j <= sqrt; j+=i) {
                        makeComposite(isPrime, j);
                    }
                }
            }
            for (; k*k <= highLimit; k+=2) {
                if (ifnotPrime(isPrime, k) == 0) {
                    primeList.add(k);
                    multipleList.add(k*k - lowLimit);
                }
            }

            for (int j = 0; j < primeList.size(); j++) {
                int f = multipleList.get(j);
                for (int n = primeList.get(j) *2; f < sieveSize; f += n) {
                    makeComposite(sieve, f);
                }
                multipleList.set(j, f - sieveSize);
            }
            int lastPrime;
            for (; p <= highLimit; p +=2) {
                if (ifnotPrime(sieve, p-lowLimit)==0) {
                    count++;
                 ```
📎 message.txt 📎 message.txt
surreal havenBOT
surreal havenBOT