Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 503. PRINT  (Citit de 9077 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
cmiN
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« : Iunie 08, 2011, 21:55:51 »

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

Am incercat asta, 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!
Memorat
DraStiK
Nu mai tace
*****

Karma: 131
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #1 : 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

Memorat
cmiN
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #2 : Iunie 09, 2011, 19:22:08 »

Zis si facut ... am implementat algoritmul in C (pentru 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 Smile.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines