Imprimă pagina - 503. PRINT

Titlul: 503. PRINT
Scris de: Cosmin Poieana din Iunie 08, 2011, 21:55:51

Stie cineva o abordare mai rapida la PRINT (https://www.spoj.pl/problems/PRINT/) decat O(t*(b-a)*sqrt(b)/2) pentru a afisa toate numerele prime dintr-un interval ?

Am incercat asta (https://ideone.com/F9u61), dar imi ia cateva secunde pe test numai pentru afisare pe cand mie trebuie sa-mi ia maxim 0.06 in medie sa se incadreze in 9-10 secunde la 150 teste maxim.

Ciur nu cred ca merge nu-ti pun la dispozitie 2gb ram, oricum am vazut best answers si de 2s cu 1.7mb am ramas oO. Am incercat si pe biti (mini ciur + verificare daca e prim cu ultimu bit ... la fel fail).

Merci anticipat!

Titlul: Răspuns: 503. PRINT
Scris de: Dragos Oprica din Iunie 09, 2011, 08:42:55

Poți încerca algoritmul probabilistic de determinare a primalității unui număr. Se numește Miller-Rabin.

Mai multe detalii aici: http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Titlul: Răspuns: 503. PRINT
Scris de: Cosmin Poieana din Iunie 09, 2011, 19:22:08

Zis si facut ... am implementat algoritmul in C (pentru problema Dk (http://infoarena.ro/problema/dk) mai intai), dar mi-l ia pe 9 ca numar prim, pana si algoritmul in sine de pe pagina lor de wikipedia.
Python putin modificat, dar structura algoritmului e aceeasi:

Cod:

import random
import math
def miller_rabin(n):
  k = 1000
  s =  max(f for f in range(0, int(math.log(n,2))) if (n-1) % 2**f == 0)
  d = (n-1) / 2**s
  for i in xrange(k):
    a = random.randrange(2, n-1)
    x = pow(a, d, n)
    if x == 1 or x == n-1:
      continue
    for r in range(1, s+1):
      if x == s:
        return False
      x = pow(x, 2, n)
      if x == 1:
        return False
      if x == n-1:
        break
  return True
print filter(miller_rabin, range(5, 100, 2))

Si implementarea in C (mai e loc de optimizari): http://pastebin.com/5e8e9dWh

Am verificat si algoritmul din pseudocod cu bazele 2 7 si 61 (care merg corect pe numere sub 4 miliarde) dar mi-l ia si aici pe 9 (posibil si altele) oricum pe problema Dk iau cateva WA in rest numai TLE :).

infoarena

infoarena - concursuri, probleme, evaluator, articole => SPOJ => Subiect creat de: Cosmin Poieana din Iunie 08, 2011, 21:55:51