C#C
C#3y ago
potzko

❔ id love to get a code review if possible

this is a segmented sieve code I wrote. it is meant to be as fast as I can get it, however id mostly like to get coding conventions for cs down

using System.Collections;
using System.Collections.Generic;

public class Primes
{
    static List<int> primes = new List<int>(new int[] { 2, 3, 5, 7 });
    static int segment = 1;
    public static void add_next_seg()
    {
        // use segmented sieve to add numbers to the prime list.
        
        //the next primes for whom we will check the squared segment
        int start = Primes.primes[Primes.segment];
        int end = Primes.primes[Primes.segment + 1];

        //create the bounds of the segment
        int seg_start = start * start;
        int seg_end = end * end;
        //create the segment, false -> prime, true -> composite
        bool[] seg = new bool[seg_end - seg_start];
        
        //the max number is seg_end which is end**2 -> only need to check primes under and including end.
        //no need to check 2, as we will jump by 2 when adding the numbers later
        for (int i = 1; i < segment + 1; i++) {
            int prime_num = Primes.primes[i];
            //start at start of segment and mark all numbers devisible by the prime number
            for (int ind = seg_start + (prime_num - (seg_start%prime_num))%prime_num; ind - seg_start < seg.Length; ind += prime_num)
            {
                seg[ind - seg_start] = true;
            }
        }
        
        //no need to check 2, as we precoded first iteration, -> start != 2 -> seg_start is odd
        for (int ind = seg_start; ind < seg_end; ind+=2)
        {
            if (!seg[ind - seg_start])
            {
                Primes.primes.Add(ind);
            }
        }
        Primes.segment++;
    }
    public static int get_nth_prime(int ind){
        //returns the nth prime
        while (Primes.primes.Count <= ind){
            Primes.add_next_seg();
        }
        return Primes.primes[ind];
    }
}
Was this page helpful?