Придумал быстрый способ создать список простых чисел - VB

Узнай цену своей работы

Формулировка задачи:

Без использования рекурсий и сложных алгоритмов нужно только указать верхнее значение MAX
Вообще я сторонник очень коротких и эффективных алгоритмов если у кого есть идеи дружите со мной!

Решение задачи: «Придумал быстрый способ создать список простых чисел»

textual
Листинг программы
Option Explicit
 
Public Function ProstChisla(Max&) As Long()
    'Возврат списка простых чисел
    Dim u&, s$, s1, i&, f&
    u = Max * 2
    ReDim Byt(u - 1) As Byte
    ReDim PrCh&(Max \ 2)
    s = Byt: s1 = ChrB(0)
    MidB$(s, 1, 1) = 1
    PrCh(0) = 1: i = 1
    While PrCh(i - 1) <= Max
        PrCh(i) = InStrB(PrCh(i - 1), s, s1)
        
        For f = PrCh(i) To u Step PrCh(i)
            MidB$(s, f, 1) = 1
        Next
        i = i + 1
    Wend
    ReDim Preserve PrCh(i - 2)
    
    ProstChisla = PrCh
End Function
 
Sub test()
Dim a
Dim b
Dim t As Single
 
t = Timer
a = ProstChisla(10000000)
Debug.Print Timer - t '10,71875
 
t = Timer
b = GetSimpleArray(10000000)
Debug.Print Timer - t '1,796875
 
End Sub
 
Public Function GetSimpleArray(Max&) As Long()
'Возврат списка простых чисел
Dim i&, f&, d&
ReDim b(1 To Max) As Byte
ReDim GSA&(1 To Max \ 2)
GSA(1) = 1
GSA(2) = 2
i = 2
d = 1
Do
  For f = GSA(i) To Max Step GSA(i) 'вычеркиваем кратные последнему простому
    b(f) = 1
  Next f
  
  For f = GSA(i) + d To Max Step 2 'ищем следующее простое число
    If b(f) = 0 Then i = i + 1: GSA(i) = f: Exit For
  Next f
  d = 2
Loop Until f > Max
ReDim Preserve GSA(1 To i)
GetSimpleArray = GSA
End Function

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

6   голосов , оценка 4 из 5
Похожие ответы