Еще одно решето для генерации простых чисел

[manan]

Всем привет. разработал алгоритм для генерации простых чисел до некоторого N. В сети попытался найти что-то похожее, но пока безрезультатно. Просьба оценить алгоритм на предмет новизны и скорости. Предлагаю уже готовую реализацию на языке java:

public class manannikovsSieveNew
{
    public static void main(String[]args)
    {
        
        long startTime=System.currentTimeMillis();
        
        // 6 <= N <= 44710000
        int N = 100000;
        
        int[] numbers = new int[N+1];
        numbers[3] = 5;
        numbers[5] = 7;
        numbers[5-1] = 3;
        
        int limit = 0;
        int prime1 = 0;
        int prime2 = 0;
        int summand = 0;
        
        int leftNumber = 3;
        int leftPrimorial  = 6;
        int rigtNumber = 0;
        int rightPrimorial = 0;
        int lastSegmentNumber = 5;
        
        int count1 = 3;
        int count2 = 0;
        
        int[] compositeNumbers = new int[(N+1)/10];
        
        boolean tr = true;
        
        while (tr == true)
        {
            rigtNumber = numbers[leftNumber];
            rightPrimorial = leftPrimorial*rigtNumber;
            
            if (rightPrimorial > N)
            {
                limit = N;
            }
            else limit = rightPrimorial;
            
            int step = 0;
            while (tr == true)
            {
                step = step + 1;
                if (step == 1)
                {
                    summand = 1;
                    prime1 = lastSegmentNumber;
                }
                else if (step == 2)
                {
                     summand = rigtNumber;    
                }
                else summand = numbers[summand];
                
                prime2 = leftPrimorial + summand;
                
                if (prime2 > limit)
                {
                    numbers[prime1] = 1;
                break;
                }
                
                numbers[prime2-1] = prime1;
                numbers[prime1] = prime2;
                
                count1 = count1 + 1;
                
                prime1 = prime2;
                lastSegmentNumber = prime2;
            }
            
            int index1 = rigtNumber;
            
            while (tr == true)
            {
                int factor1 = index1;
                int compositeNumber1 = factor1*factor1;
                if (compositeNumber1 > limit)
                {
                break;    
                }
                
                int compositeNumbersCount = 0;
                
                int index2 = index1;
                while (tr == true)
                {
                    int factor2 = index2;
                    int compositeNumber2 = factor1*factor2;
                    if (compositeNumber2 > limit)
                    {
                    break;    
                    }
                    
                    compositeNumbersCount = compositeNumbersCount + 1;
                    
                    compositeNumbers[compositeNumbersCount] = compositeNumber2;
                    
                    count2 = count2 + 1;
                    
                    index2 = numbers[index2];                   
                
                }
                
                for (int n = 1; n <= compositeNumbersCount; n++)
                {
                    int x = numbers[compositeNumbers[n]-1];
                    int у = numbers[compositeNumbers[n]];
                
                numbers[x]   = у;
                numbers[у-1] = x;
                
                }
                
                index1 = numbers[index1];
                
                if (rightPrimorial <= N)
                {
                break;    
                }
                
            }
            
            if (rightPrimorial > N)
            {
            break;    
            }
            
            leftNumber = rigtNumber;
            leftPrimorial = rightPrimorial;

        }

        long finishTime=System.currentTimeMillis();
        long countMS = finishTime - startTime;
        System.out.println();
        System.out.print(countMS/1000 + " secunds");
        System.out.println();
        System.out.print(countMS + " millisecunds");
        System.out.println();

        int PrimesCount = 0; // number 2 and number 3
        int a = 2;
        int b = 4;
        
        while (a > 1)
        {
            
            //here you can print primes
            //System.out.println();
            //System.out.print(a);
            
            PrimesCount = PrimesCount + 1;
            a = numbers[b];
            b = a;
           
        }
        
        System.out.println();
        System.out.println();
        System.out.print(PrimesCount + " primes to " + N);       
                    
    }

}

Deggial: код оформляйте тегом code

[whitefox]

Почему бы Вам самому не сравнить Ваш алгоритм с решетом Эратосфена по затратам времени и, особенно, памяти?

Вот и программка на С++

Используется синтаксис C++

#include <iostream>
#include <ctime>

using namespace std;


int main(){     
        unsigned N = 1000000; //N >= 2
        unsigned max = (N + 1) >> 1;            
        unsigned char* feld = new unsigned char[max];
        feld[0] = 1;
        for(unsigned i = 1; i < max; i++) feld[i] = 0;  
        unsigned sqrmax = (unsigned)sqrt((double)N);            
        double begin = clock();
        for(unsigned teste = 3; teste <= sqrmax; teste += 2){
                if(feld[teste >> 1]) continue;
                for(unsigned i = teste * teste, t = teste << 1; i <= N; i += t)
                      feld[i >> 1] = 1;                                 
        }
        clock_t endcl = clock();
        unsigned count = 1;
        for(unsigned i = 1; i < max; i++) if(!feld[i]) count++;
        cout << count << " prime numbers foundn "
              << ((endcl - begin) / CLOCKS_PER_SEC) << " secs\n";       
        delete[] feld;  
        return 0;
}

Сколько, например, займёт времени поиск всех простых меньших миллиарда?