Нахождение простых чисел. Оптимизация

[JackDaniels]

Интересно было бы поставить задачу по числам Мерсенна, и профит не плохой и задача не тривиальная.

[OmoN]

Еще одно решение. До 100 000 работает 1,03-1,04 секунды.

PHP код:

function IsPrime(n:integer):boolean;
  var r:boolean;
       i:integer;
begin
 r := true;
 i := 3;
 while(i <= sqrt(n))do begin
   if((n mod i) = 0)then begin
     r := false;
     break;
   end;
   i := i+2;
 end;
 result := r;
end;

procedure FindPrimes(maxNumber:integer);
  var i: integer;
       label lab;
begin
 i := 3;
 WriteLn('BEGIN');
 WriteLn('2');
 WriteLn('3');
 while(i<=maxNumber)do begin
   if(i>3)and(i mod 3 = 0)then goto lab;
   if(i>5)and(i mod 5 = 0)then goto lab;
   if(i>7)and(i mod 7 = 0)then goto lab;
   if(((i-1) mod 6)*((i+1) mod 6) = 0)and(i>3) then
     if(IsPrime(i))then WriteLn(i);
   lab:
   i := i+2;
 end;
 WriteLn('END');
end; 


[Evgeniy Sklyarevskiy]

Сообщение от OmoN

До 100 000 работает 1,03-1,04 секунды.

И как там Пи? чему равно по новым данным?

[Rooslan Khayrov]

Сообщение от Evgeniy Sklyarevskiy

И напоминаю про Скатерть Улама, у кого есть время машинное!

Да пожалуйста:
https://gist.github.com/970169

import Data.List
import Graphics.Gloss
import Graphics.Gloss.Data.Point

infixl 6 |+|

(x, y) |+| (x', y') = (x + x', y + y')

spiral = scanl (|+|) (0, 0) steps
    where
        steps = concat $ zipWith replicate sides (iterate r90ccw (1, 0))
        sides = concatMap (replicate 2) $ map fromIntegral [1..]
        r90ccw (x, y) = (-y, x)

primes :: [Int]
primes = 2 : 3 : filter isPrime [5, 7 ..]
    where 
        isPrime n = and [n `mod` i /= 0 |
            i <- takeWhile (\i -> i * i <= n) (tail primes)]

primesMask = merge [1..] primes
    where
        merge (n : nt) ps@(p : pt)
            | n == p    = True : merge nt pt
            | otherwise = False : merge nt ps

side = 600

picture = color black $ pictures $ [translate x y (rectangleSolid 1 1) |
    (x, y) <- takeWhile isVisible $ filteredSpiral]
    where
        filteredSpiral = map fst $ filter snd $ zip spiral primesMask
        isVisible p = pointInBox p (side, side) (-side, -side)

main = displayInWindow "Ulam spiral" windowSize (100, 100) white picture
    where windowSize = (round side, round side)

Алгоритм наивный, не решето, но на помещающихся в экран объёмах и такой справляется.

[Evgeniy Sklyarevskiy]

Сообщение от Rooslan Khayrov

Да пожалуйста:

Отлично, спасибо!

Теперь осталось объяснить происхождение явно выделенных диагональных отрезков и мы в дамках! :-0)

[Наташа]

Сообщение от German Stimban

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

Да, конечно выкладывайте

[Наташа]

Сообщение от Evgeniy Sklyarevskiy

Теперь осталось объяснить происхождение явно выделенных диагональных отрезков и мы в дамках! :-0)

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

[Evgeniy Sklyarevskiy]

Сообщение от Наташа

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

Хотите сказать, что диагональные под 45 градусов линии я придумал? Рассмотрите крупно картинку, они там есть! Гарднер объяснял это семейством простых чисел, порождаемых уравнениями вроде x^2 + x + 41 - дает подряд много простых чисел, лежащих на диагонали. Объяснить эту визуализацию каких-то закономерностей пока никто не может.

[JackDaniels]

Сообщение от Evgeniy Sklyarevskiy

Хотите сказать, что диагональные под 45 градусов линии я придумал? Рассмотрите крупно картинку, они там есть! Гарднер объяснял это семейством простых чисел, порождаемых уравнениями вроде x^2 + x + 41 - дает подряд много простых чисел, лежащих на диагонали. Объяснить эту визуализацию каких-то закономерностей пока никто не может.

Да, это не просто белый шум, в нем явно прослеживаются четкие диагонали.

[Evgeniy Sklyarevskiy]

Мы на пороге великого открытия, осталось самую малость.... проследить и объяснить :-0)