В продолжение темы: быстрая генерация простых чисел

ОПИСАНИЕ КЛАССА НА ЯЗЫКЕ JAVA ДЛЯ ГЕНЕРАЦИИ ВСЕХ ПРОСТЫХ ЧИСЕЛ ДО N:

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);       
                    
    }

}


ОПИСАНИЕ ПРОЦЕДУР В МОДУЛЕ ФОРМЫ ОБРАБОТКИ В СРЕДЕ 1С:ПРЕДПРИЯТИЕ 8.2 ДЛЯ ГЕНЕРАЦИИ ВСЕХ ПРОСТЫХ ЧИСЕЛ ДО N:

Процедура ОтметитьСоставные(Числа, ИндексНач, Гран, Единожды)
    
    Индекс1 = ИндексНач;
    Пока Истина Цикл
        
        Множитель1 = Индекс1;
        Если Множитель1*Множитель1 > Гран Тогда
            Прервать;
        КонецЕсли;
        
        Составные = Новый Массив;
        Индекс2 = Индекс1;
        Пока Истина Цикл
            Множитель2 = Индекс2;
            Составное = Множитель1*Множитель2;
            Если Составное > Гран Тогда
                Прервать;
            КонецЕсли;
            
            Составные.Добавить(Составное);            
            Индекс2 = Числа[Индекс2];
            
        КонецЦикла;
        
        Для Каждого Составное ИЗ Составные Цикл
            
            ПсевдоПростоеПред = Числа[Составное-1];
            ПсевдоПростоеСлед = Числа[Составное];
            
            Числа[ПсевдоПростоеПред]   = ПсевдоПростоеСлед;
            Числа[ПсевдоПростоеСлед-1] = ПсевдоПростоеПред;
                                
        КонецЦикла;
        
        Индекс1 = Числа[Индекс1];
        
        Если Единожды Тогда
            Прервать;
        КонецЕсли;
        
    КонецЦикла;
    
    
КонецПроцедуры    

Функция ПолучитьГраницу(Числа, ИндексПрав)
    
    Гран = 1;
    Для Индекс = 0 ПО ИндексПрав Цикл
        Гран = Гран * Числа[Индекс];        
    КонецЦикла;    
    Возврат Гран;
    
КонецФункции

ПРОЦЕДУРА ГЕНЕРАЦИЯ()
    
    ВремяНачала = ТекущаяДата();
    Сообщить(Символы.ПС);
    Сообщить("Начало: " + ВремяНачала);
    
    Числа = Новый Массив(Граница+1);
    Числа[3] = 5;
    Числа[5] = 7; Числа[5-1] = 3;
        
    ЧислоЛев             = 3;
    ГраницаЛев           = 6;
    ЧислоПрошлогоОтрезка = 5;
    
    Пока Истина Цикл
        
        ЧислоПрав = Числа[ЧислоЛев];
        ГраницаПрав = ГраницаЛев*ЧислоПрав;
        Гран = ?(ГраницаПрав > Граница, Граница, ГраницаПрав);
        
        Шаг = 0;
        Пока Истина Цикл
            Шаг = Шаг + 1;
            
            Если Шаг = 1 Тогда
                Слагаемое = 1;
                ПсевдоПростоеПред = ЧислоПрошлогоОтрезка;
            ИначеЕсли Шаг = 2 Тогда
                Слагаемое = ЧислоПрав;        
            Иначе
                Слагаемое = Числа[Слагаемое];
            КонецЕсли;
            
            ПсевдоПростоеСлед = ГраницаЛев + Слагаемое;
            
            Если ПсевдоПростоеСлед > Гран Тогда
                Числа[ПсевдоПростоеПред] = 1;
                Прервать;
            КонецЕсли;
            
            Числа[ПсевдоПростоеСлед-1] = ПсевдоПростоеПред;
            Числа[ПсевдоПростоеПред] = ПсевдоПростоеСлед;

            ПсевдоПростоеПред = ПсевдоПростоеСлед;
            ЧислоПрошлогоОтрезка = ПсевдоПростоеСлед;
        КонецЦикла;
        
        Если ГраницаПрав > Граница Тогда
            ОтметитьСоставные(Числа, ЧислоПрав, Гран, Ложь);
            Прервать;
        Иначе
            ОтметитьСоставные(Числа, ЧислоПрав, Гран, Истина);
        КонецЕсли;
                
        ЧислоЛев = ЧислоПрав;
        ГраницаЛев = ГраницаПрав;
        
    КонецЦикла;
    
    ЧислоПростых = 1; // число 2
    ПростоеПосле = 0;
    ПростоеДо = 3;
    Пока НЕ ПростоеПосле = 1 Цикл
        ЧислоПростых = ЧислоПростых + 1;
        ПростоеПосле = Числа[ПростоеДо];
        ПростоеДо = ПростоеПосле;
    КонецЦикла;
    
    ВремяОкончания = ТекущаяДата();
    Сообщить("Окончание: " + ВремяОкончания);
    Сообщить("Число простых до " + Граница + ": " + ЧислоПростых);    
    Сообщить("Время выполнения : " + (ВремяОкончания - ВремяНачала) + " секунд");
    
КОНЕЦПРОЦЕДУРЫ

Спасибо. А зачем?

(1) может, кто-то возьмется оценить сложность алгоритма. было бы очень интересно.

а в чем смысл вообще?
что-то меня стиль "пока истина" убивает

словами описать

(0) а зачем ява то? уж проще тогда на С# - его проще во внешнюю компоненту запихнуть...

(3) не смущайтесь, это мой первый код на java, просто хотел чтобы идею смогли "прощупать" не только 1с-ники

(3) в первом приближении: генерируется возрастающая последовательность чисел до N, где присутствуют ВСЕ простые числа до N, а также составные, которые потом исключаются по некоторому алгоритму. "решето", в-общем.

(0) это чтобы добывать биткоины в среде 1С ?

(7) приближение второе. Рассматриваем только N>6. Отрезок (6; N) разбиваем на несколько отрезков, точками разбиения служат последовательные праймориалы: 6 = 2*3, 30 = 2*3*5, 210 = 2*3*5*7, 2310 = 2*3*5*7*11 и т.д. Например, если N = 1000, получаем отрезки (6, 30], (30, 210], (210, 1000]. Далее эти отрезки последовательно "отрабатываются".

Сферический конь в вакууме.

(10) т.е.?

(9) описанный способ генерации простых можно назвать улучшенным решетом Эйлера, описание стандартного решета Эйлера хорошо дано в википедии: wiki:Решето_Эратосфена
Оно короткое, приведу целиком здесь:
Решето Эйлера

Решето Эйлера это вариант решета Эратосфена, в котором каждое составное число удаляется из списка только один раз.

Составляется исходный список начиная с числа 2. На каждом этапе алгоритма первый номер в списке берется как следующее простое число, и определяются его произведения на каждое число в списке которые маркируются для последуюшего удаления. После этого из списка убирают первое число и все помеченные числа, и процесс повторяется вновь:

[2] (3) 5  7  9 11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
[3]    (5) 7    11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
[4]       (7)   11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
[5]            (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
[...]

Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после k-го этапа рабочий список содержит только числа взаимно простые с первыми k простыми числами (то есть числа не кратные ни одному из первых k простых чисел), и начинается с (k+1)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.

Какова скорать алгоритма? N^2, 2^N или хуже?
Каково потребление памяти?

(9) Решето Эратосфена

import java.util.*;

/**
* Эта программа выполняет тест "решето Эратосфена", подсчитывая
* простые числа до 1 000 000.
* @version 1.0
* @author NA
*/
public class Eratosphen
{
    public static void main(String[] args)
    {
        int n = 1000000;
        long start = System.currentTimeMillis();
        BitSet b = new BitSet(n + 1);
        int count = 0;
        int i;
        for (i = 2; i <= n; i++)
            b.set(i);
        i = 2;
        while (i * i <= n)
        {
            if (b.get(i))
            {
                count++;
                int k = 2 * i;
                while (k <= n)
                {
                    b.clear(k);
                    k += i;
                }
            }
            i++;
        }
        
        while (i <= n)
        {
            if (b.get(i)) count++;
            i++;
        }
        
        long end = System.currentTimeMillis();
        System.out.println(count + "простых чисел");
        System.out.println((end - start) + "мс");
    }
}

(15) до 40 000 000 моим методом: 1157 millisecunds, твоим эратосфеном: 3585мс

(15) Да, у меня 887 мс твоим способом, моим 1930. Малаца!

(12) "улучшение" заключается в том, что в отличие от обычного решета Эйлера исходный список чисел формируется не весь сразу, а "отрезками" (см. 9), и уже "очищенным" от большого количества составных чисел.

вообще, хотелось бы выяснить, есть ли нечто новое в данном алгоритме или я изобрел "велосипед".

коллеги, где Вы? есть какие мнения?

(18) Особо нового нет. И праймориалы использовать дальше 7-и или 11-и смысла нет - слишком быстро падает профит и слишком быстро растут накладные расходы на них.

(19) Про медицину еще спроси, получишь квалифицированный ответ... Ну и с другой стороны ужа давно всё изобретено... Так просто уже ничего не придумаешь.

(18) Вдогонку: с простыми числами, пока первые числа влезают в память и само число в целую размерность, вообще не сильно интересно, особенно, если идти по протоптанным алгоритмам.