» »

pra števila..

pra števila..

1
2
»

tx-z ::

in kdaj lahk prčakujemo ta program?
tx-z

Thomas ::

ASAP. Se ne obvežem zelo - ampak ASAP.

:)
Man muss immer generalisieren - Carl Jacobi

tx-z ::

ASAP ???? kaj je to?
tx-z

Gandalfar ::

As Soon As Possible :)

Thomas ::

Tale tanova metoda za določevanje, če je neko število praštevilo, ni _praktično_ tako zelo učinkovita sploh!

Šele na "milijardah bitov" ali kaj takega dohiti in prehiti druge metode.

Za tolažbi tale POVEZAVA NA FAKTORIZACIJO.

Obilo zabave. :)
Man muss immer generalisieren - Carl Jacobi

rsaver ::

Tu mas source v C++!


/ Napišite funkcijo, ki prejme naravno število in vrne logično
// vrednost, ki pove, ali je dano število praštevilo.
// V glavnem programu preberite število in kličite funkcijo.



#include

bool pra(int a, int b , int c)
{
int i=0; //Prireditev spremenljivk
int s=0;
int j=0;
while (i<=a) //zanka while preverja
{ //ce je ostanek pri deljenju enak 0,ce je
i++; //se s povecuje
if ( a % i == 0 )
{
s += j;
j++;
}
}
if (s<=2)return true; //ce je s manjsi ali enak dva naj
else return false; //vrne true ,ce ni pa false;
}

int main()

//deklaracija spremenljivk
{int a,b,c;
// deklaracija vrednosti spremenljivke
//Postopek za vpis stevila

cout<<"Vpisite naravno stevilo"< cin>>a;
cout< pra ( a , b , c ); //klicanje funkcije
if (pra(a,b,c)==true) cout<<"Stevilo je prafaktor!"; //preveri ali je
else cout<<"To stevilo ni prafaktor"; //a pafaktor ali ni
return 0;
}

Thomas ::

rsaver

Tale tvoj algoritem ni ravno najbolj optimalen. Šteješ koliko števil od 2 do N, N-ja ne deli.

Vsaj dve izboljšavi sta takoj. Ko naleti na prvega delitelja napiše "SESTAVLJEN" in break;.

Druga izboljšava je pa ta, da greš samo do SQRT(N).

Za približno MILIJON veliko število ti rabiš cca milijon korakov.

Tile dve izboljšavi zmanjšata to število na največ tisoč korakov.

Pa imamo še vedno za velika števila neuporaben program.

:)



Man muss immer generalisieren - Carl Jacobi

Thomas ::

Zraven zgornjega linka je še tale, ki vsebije source v javi.

:)
Man muss immer generalisieren - Carl Jacobi

CHAOS ::

No, spisal sem programček za računanje s pomočjo tiste funkcije od prej ter ugotovil, da mi računa samo do N=19, potem pa se mu začne rahlo trgati. No, verjetno je to zato, ker je 20! pribl. 10 ^18, long v javi pa je pribl. 10^19.
Kako zaobiti ta problem ter kako potem računajo praštevila večja od 10^308 (double) ?
Seveda je jasno, da ne uporabljajo te funkcije, ampak vseeno? :8)

PS. Thomas: A že pišeš source? :)
'They have computers, and they may have other weapons of mass destruction.'

Thomas ::

Jutri zvečer ga pošljem Primožu. Executable. Ki pa piše komentarje, kaj dela.

Vendar ni na mojo zgornjo funkcijo ampak na tisti indijski Prime in P, ki sem ga dal (algoritem) nekoliko nižje spodaj.

Nisem pa delal svoje multibitne aritmetike - preveč dela to - zato funciona samo do 1018.



Med pisanjem sem našel celo napakico v algoritmu in jo popravil. :))

p.s.

Sicer mi je Primož rekel da lahko uploadam - ampak ne znam.

Al pa ga nisem prav zastopil. Nima veze.











Man muss immer generalisieren - Carl Jacobi

Thomas ::

Ja. Sem pršu do sklepa, da tale tanovi algoritem sicer dela. Ampak niti pribložno ne tako, kot govorijo njegovi avtorji.

Na strani 4. pdfja.

Takle output da program ki sem ga napisal, za 2003:

-------------------------------------------------------
[1] Is ( n is of the form a^b , b > 1 ) ???

2 44^2 = 1936 <> 2003
3 12^3 = 1728 <> 2003
4 6^4 = 1296 <> 2003
5 4^5 = 1024 <> 2003
6 3^6 = 729 <> 2003
7 2^7 = 128 <> 2003
8 2^8 = 256 <> 2003
-------------------------------------------------------
[2] R=2
[3] While (R < SQRT( 2003))
[4] Is ( GDC( 2003, 2) >1 ???
2 is prime, therefore calculate Q - the largest prime factor of 1
[4] Is ( GDC( 2003, 3) >1 ???
3 is prime, therefore calculate Q - the largest prime factor of 2
[4] Is ( GDC( 2003, 4) >1 ???
[4] Is ( GDC( 2003, 5) >1 ???
5 is prime, therefore calculate Q - the largest prime factor of 4
Q = 2
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 2 >= 67
[4] Is ( GDC( 2003, 6) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 2 >= 74
[4] Is ( GDC( 2003, 7) >1 ???
7 is prime, therefore calculate Q - the largest prime factor of 6
Q = 3
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 80
[4] Is ( GDC( 2003, 8) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 86
[4] Is ( GDC( 2003, 9) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 91
[4] Is ( GDC( 2003, 10) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 96
[4] Is ( GDC( 2003, 11) >1 ???
11 is prime, therefore calculate Q - the largest prime factor of 10
Q = 5
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 100
[4] Is ( GDC( 2003, 12) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 105
[4] Is ( GDC( 2003, 13) >1 ???
13 is prime, therefore calculate Q - the largest prime factor of 12
Q = 3
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 109
[4] Is ( GDC( 2003, 14) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 113
[4] Is ( GDC( 2003, 15) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 117
[4] Is ( GDC( 2003, 16) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 121
[4] Is ( GDC( 2003, 17) >1 ???
17 is prime, therefore calculate Q - the largest prime factor of 16
Q = 2
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 2 >= 125
[4] Is ( GDC( 2003, 18) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 2 >= 129
[4] Is ( GDC( 2003, 19) >1 ???
19 is prime, therefore calculate Q - the largest prime factor of 18
Q = 3
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 132
[4] Is ( GDC( 2003, 20) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 135
[4] Is ( GDC( 2003, 21) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 139
[4] Is ( GDC( 2003, 22) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 142
[4] Is ( GDC( 2003, 23) >1 ???
23 is prime, therefore calculate Q - the largest prime factor of 22
Q = 11
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 11 >= 145
[4] Is ( GDC( 2003, 24) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 11 >= 148
[4] Is ( GDC( 2003, 25) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 11 >= 152
[4] Is ( GDC( 2003, 26) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 11 >= 155
[4] Is ( GDC( 2003, 27) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 11 >= 158
[4] Is ( GDC( 2003, 28) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 11 >= 160
[4] Is ( GDC( 2003, 29) >1 ???
29 is prime, therefore calculate Q - the largest prime factor of 28
Q = 7
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 7 >= 163
[4] Is ( GDC( 2003, 30) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 7 >= 166
[4] Is ( GDC( 2003, 31) >1 ???
31 is prime, therefore calculate Q - the largest prime factor of 30
Q = 5
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 169
[4] Is ( GDC( 2003, 32) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 172
[4] Is ( GDC( 2003, 33) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 174
[4] Is ( GDC( 2003, 34) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 177
[4] Is ( GDC( 2003, 35) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 179
[4] Is ( GDC( 2003, 36) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 182
[4] Is ( GDC( 2003, 37) >1 ???
37 is prime, therefore calculate Q - the largest prime factor of 36
Q = 3
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 184
[4] Is ( GDC( 2003, 38) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 187
[4] Is ( GDC( 2003, 39) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 189
[4] Is ( GDC( 2003, 40) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 3 >= 192
[4] Is ( GDC( 2003, 41) >1 ???
41 is prime, therefore calculate Q - the largest prime factor of 40
Q = 5
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 194
[4] Is ( GDC( 2003, 42) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 5 >= 197
[4] Is ( GDC( 2003, 43) >1 ???
43 is prime, therefore calculate Q - the largest prime factor of 42
Q = 7
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 7 >= 199
[4] Is ( GDC( 2003, 44) >1 ???
Whether or not, Q > 4*(R^1/2)*LOG(N), that is 7 >= 201




Ključni pogoj Q>4*(R^1/2)*log(N) ni nikoli izpolnjen. Vsaj za 2003 ne.

Torej je cela zadeva brezpredmetna. Dela tako, da preveri vse deljitelje do korena. Kar zna narest vsak. Vsaj za 2003, dela tako - in še za mnoge druge.

:|

p.s.

Dopuščam da se motim. Da sem nekaj spregledal. Ampak ne verjamem, da se res.

Grem gledat mal po netu, kaj pravijo drugi.
Man muss immer generalisieren - Carl Jacobi

Thomas ::



Tole naj bi bil tale algoritem.

Meni smrdi, odkar sem ga implementiral.

:|
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Heh, kretenčkov!

Tuki (str. 4) sem šele videl, da LOG pomeni dvojiški logaritem, ne naravni.

Samo to še NIČ ne pomaga, samo po sebi.

:|
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Hja .. zdej mi je jasno.

Da bi izračunali za število okoli 1000, če je praštevilo ali ne, nam tale algoritem garantira:

(ln2(1000))^12 =~ 10^12 korakov.

Mislim ej - hvala lepa.


Za gugol (10^100) pa

ln2(gugol)^12 =~ 10^30 korakov.

Mislim ej - hvala lepa!


za 10^milijon pa 36 milijonov korakov, kar pa je že zelo ugodno.


Samo zato rabiš pa multibitno aritmetiko.


Jest sem s temle (zaenkrat) over&out.

:)
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

CHAOS ::

Thomas: Kaj je to multibitna aritmetika oziroma kje lahko izvem kaj več o tem kako to narediti? :D
'They have computers, and they may have other weapons of mass destruction.'

Thomas ::

Povezava na 1024 bitno aritmetiko.

To omogoča računanje s 300 mestnimi števili.

En dober PC pod Windowsi pa bi načelno (s primernim programom seveda) lahko omogočal manipulacijo milijardo bitnih ali 300 milijonov mestnih števil.


Muštr za program je lahko ročni algoritem za pismeno množenje, deljenje, seštevanje in odštevanje.

:)

p.s.

Še o napaki algoritma, o kateri sem govoril:

Namesto:

While (r < n)

bi moralo biti

While (r < Sqrt(n))

;)
Man muss immer generalisieren - Carl Jacobi

asPeteR ::

Thomas:
Tale source v Javi je kar zanimiv ... Le komu se je dalo tole pisat ...
:\
No v glavnem ima pa eno napakico.
V metodi startNewFactorization je "napaka" v teli vrstici:
ExpressionRC = expression.ComputeExpression(textNumber.getText().trim(),0,ExpressionResult);

Napaka pa je ! Ne najde ga. Ta expression pa ni API od Jave ... Tko, da ne vem kaj bi to lahko bilo? Mogoce ves?

:|

Thomas ::

Najprej popravek:

Thomas

> za 10^milijon pa 36 milijonov korakov, kar pa je že zelo ugodno.

bi MORALO biti

> za 10^milijon pa 10^72 korakov, kar pa je že zelo ugodno.


asPeter

<>ComputeExpression je metoda jave, ki ti naprimer string "16*5+1" pretvori v 81.

Je pa še nekaj drugega čudno pri tem sourcu ... gledamo ... najbrž ni dal ravno najbolj delujočega listinga.

:)
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Thomas ::

Z enim klicajem in dvema slashoma smo dosegli, da Java program dela. (Thanx nevone!)

Poslal ga bom Primožu - pronto.

(.java .class .html)

:)
Man muss immer generalisieren - Carl Jacobi

CHAOS ::

Ko smo že pri praštevilih, pa naj bo še besedica o praštevilskih parih. Dve praštevili sta par, če se razlikujeta za a=b-2 (a
Tole so pari z intervala [999990000,999999999]:

999990419 , 999990421
999990569 , 999990571
999990581 , 999990583
999990851 , 999990853
999990911 , 999990913
999991061 , 999991063
999991229 , 999991231
999991919 , 999991921
999992099 , 999992101
999992129 , 999992131
999992639 , 999992641
999993581 , 999993583
999993719 , 999993721
999993821 , 999993823
999993899 , 999993901
999994157 , 999994159
999994379 , 999994381
999994649 , 999994651
999994691 , 999994693
999995627 , 999995629
999996029 , 999996031
999996071 , 999996073
999996707 , 999996709
999997769 , 999997771
999998141 , 999998143
999998507 , 999998509
999998639 , 999998641
999998687 , 999998689
999998957 , 999998959
999999191 , 999999193

Sedaj me pa zanima sledeče. Povsem jasno je, da je naravnih števil neskončno. Težje razumljivo je, da je tudi praštevil neskončno. Ali je potem tudi praštevilskih parov neskončno?

'They have computers, and they may have other weapons of mass destruction.'

Thomas ::

Evklid je rekel takole:

Pa recimo da imamo samo neko končno število praštevil. Da je vsako naravno število deljivo z vsaj enim od njih!

Potem jih pa ta praštevila zmnožimo in prištejmo 1. Dobimo število S.

Če tako dobljeno število S delimo s katerimkoli teh praštevil, dobimo ostanek 1. Torej ali je praštevilo in/ali pa naš spisek ni bil popoln, pa kakršenkoli je že bil.

Temu se reče Evklidov izrek.

Če je t.i. dvojčkov tudi neskončno (znotraj tega aksiomatskega sistema) se pa ne ve. Misli se, da najbrž da jih je.

:)


Man muss immer generalisieren - Carl Jacobi

asPeteR ::

Thomas:

Ja, micken sem cudn vprasu. Men ni jasno kje je ta objekt expression. Ker ne ga nikjer ni!
To mi ni jasn. Ker metoda ComputeExpression se mora nanasati na ta objekt ...

Thomas ::

Na, ti pošljem po mailu 5 min od zdej.

HTML pelji v browser, glej source ...

Mislim da ti bo vse jasno.

:)
Man muss immer generalisieren - Carl Jacobi

asPeteR ::

Thomas:

Tnx! Jah, zdej pa dela, valda ker je zdej tist "sumljiv" del kode zakomentiran ... :D

Kakorkolize itak je ta del na try, catch varjanto. Ucer pa to sem spregledal ...

0:)

fx ::

Program ali knjiznica za izračuna največji skupni deljitelj danih števil a in b, obstaja ali ne obstaja - ali drugače povedano ali obstaja knjižnica ali program ki uporablja Evklidov algoritem ?

lp

"UNIX & C++"

Arthur ::

algoritem za izračun največjega skupnega delitelja obstaja.

Evklidov je pa samo izrek, samo dokaz da je praštevil neskončno, tu ne gre za noben algoritem! ga tudi ne more biti, saj tudi ni nikakršnega spiska vseh praštevil..

Primoz ::

Arthur Dent ... ne zavajaj.

Euclid's algorithm
stran na planetmath.org
There can be no real freedom without the freedom to fail.

Zgodovina sprememb…

  • spremenil: Primoz ()

Arthur ::

res, spet sem prehitro zinil, brez da bi prej dovolj razmislil, ali preveril.

pri največjem skupnem delitelju sem mislil na tole:

int gcd(a, b)
{
if (b==0)
return a;
else
return gcd(b, a mod b);
}

, kar je ravno Evklidov algoritem... samo da sem že pozabil, da se tako imenuje.

sicer pa sem tudi njegovo vprašanje najbrž narobe razumel, ko je spraševal o Evklidovem algoritmu, in to povezal z izrekom par postov više, ki pač ni algoritem.

Zgodovina sprememb…

  • spremenil: Arthur ()

Yacked2 ::

Si bom kar sposodil temo. Moja koda v Pyhton-u za "odkrivanje" praštevil:

SteviloZaTest = int(raw_input("Vnesite stevilo za test: "))
a = SteviloZaTest + .0
b = 2

while(b!=a):
    if (a / b) == (SteviloZaTest/b):
        print str(SteviloZaTest) + ' ni prastevilo!'
        print 'Deljivo je z ' + str(b)
        break
    
    elif ( a == b):
        print str(SteviloZaTest) + ' je prastevilo!'
        break
    
    else:
        b = b +1


Če število ni praštevilo ti izpiše prvi možni deljitel ter zanko ustavi. če je število praštevilo ne izpiše ničesar. Alogaritem deluje do neke meje, potem se pa pokvari -.-
1
2
»


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Python

Oddelek: Programiranje
202410 (1096) d_DJ
»

matematika-zaporedja (strani: 1 2 )

Oddelek: Šola
564808 (3644) lebdim
»

Casovna kompleksnost algoritma

Oddelek: Programiranje
71148 (903) lebdim
»

Random

Oddelek: Znanost in tehnologija
434084 (3314) Thomas
»

Neskončno... (strani: 1 2 )

Oddelek: Loža
616147 (5061) Gh0st

Več podobnih tem