Numere prime; factorizare

[emi]

Un numar prim este un numar natural (0,1,2, ... , n, ... infinit) care are proprietatea de a se divide doar cu 1 si el insusi. Adica daca il imparti la oricare alt numar natural mai mic ca el, nu obtii rest 0.

S-a mai pus problema: cum se poate factoriza un numar.
Cei care au citit The Art Of Computer Programming, stiu deja ca sunt mai multi algoritmi.

Pentru numere mici, cel mai eficient e cel de tip "brute force".
Adica ai un numar pe 32 de biti, si il imparti la toate numerele prime pe 16 biti.

nu trec la detalii pina nu vad ce parere aveti.

[Archangel]

doar o mica observatie, 2 este cel mai mic numar prim, si singurul par, deci 0 si 1 nu sunt numere prime

[emi]

doar o mica observatie, 2 este cel mai mic numar prim, si singurul par, deci 0 si 1 nu sunt numere prime

scuze pentru lipsa de exactitate in exprimare, numerele naturale incep cu 0 (conform axiomei), si se incrementeaza cu 1, pina la infinit.
O data, chiar un asistent universitar avea o problema, daca multimea numerelor naturale e infinita sau nu.

sa fiu rau ?

axioma(nr x chiar ca nu i-mi mai amintesc, da e pe acolo): orice numar natural are un succesor, adica dat fiind numarul natural n, exista si n+1,

Sa presupunem prin absurd ca multimea numerelor naturale ar fi finita. Inseamna ca exista n, care e cel mai mare numar natural. Conform axiomei, presupunerea e falsa, pentru ca exista n+1. qed.

[Archangel]

scuze, inseamna ca am inteles eu gresit cand ai inceput cu "un numar prim este..."

[AnaKonD]

Si cerinta clara a concursului este...?

Ps: pune eticheta de incepator sau avansat ,etc. in titlu

[emi]

Si cerinta clara a concursului este...?
Ps: pune eticheta de incepator sau avansat ,etc. in titlu

Nu vroiam eticheta de concurs pe acest subiect. A mai fost un concurs pe tema asta, si acel subiect e inchis.
Am intrebat de ce sunt inchise asa de multe subiecte, si daca pot deschide unul nou pe tema asta.
Sigur nu s-a spus tot ce se poate spune despre acest subiect.

Deci acesta nu e un concurs, e o tema pentru cei interesati.

Eu am deja programele pentru factorizare scrise in pascal si assembler. In plus am gasit o metoda de a stoca toate numerele prime pe 16 de biti (adica peste 6 mii) ca sa ocupe cit mai putin.

[AdyX]

Pai... aici e sectiunea de competitii - programare. Aici se posteaza doar concursuri. E drept ca nici eu nu am fost atent cand ti-am raspuns, si imi cer scuze pentru confuzie.

[AnaKonD]

^^ sunt inchise deoarece s-au terminat acele concursuri. Este mai ordonat asa nu crezi? Cat despre subiecte, poti oricand sa deschizi unul la Algoritmi si tehnici de programare si sa-l dezbati acolo.

[emi]

Am stabilit ca cel mai eficient algoritm de factorizare pentru numere mici e cel de tip "brute force" adica stim toate numerele prime mai mici decit radical din acel numar.
Pentru numere pe 32 de biti e suficient sa stii toate numerele prime pe 16 biti.
diferenta intre 2 numere prime impare e un numar par.
deci e suficient sa stim jumatarea diferentei intre 2 numere prime.
si de aici algoritmul.
am studiat, si am aflat ca diferenta intre 2 numere prime consecutive pe 32 de biti e mai mica de 512
deci diferenta lor impartita la 2 incape pe un byte.

[emi]

In acest fel toate numerele prime pe 32 de biti pot fi memorate pe mai putin de jumatate de CD.
Eu am facut acest program in pascal cu asm. Nu mai am sursele originale, din diverse motive. Ideile ramin. Si se pot rescrie.
( din cite i-mi mai amintesc era ceva un pic peste 240 de megi )

[HostGator]

Ai auzit de aligatorul care ofera hosting?