pra števila.. @ Slo-Tech

Forum » Znanost in tehnologija »
pra števila..

pra števila..

« 1

tx-z :: 19. dec 2002, 15:10

in kdaj lahk prčakujemo ta program?

tx-z

Thomas :: 19. dec 2002, 16:36

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

Man muss immer generalisieren - Carl Jacobi

tx-z :: 19. dec 2002, 19:53

ASAP ???? kaj je to?

tx-z

Gandalfar :: 19. dec 2002, 19:54

As Soon As Possible :)

Thomas :: 20. dec 2002, 15:49

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 :: 20. dec 2002, 17:57

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 :: 20. dec 2002, 18:38

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 :: 20. dec 2002, 18:41

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

Man muss immer generalisieren - Carl Jacobi

CHAOS :: 21. dec 2002, 22:10

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 :: 21. dec 2002, 22:22

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 10¹⁸.

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 :: 22. dec 2002, 19:49

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 :: 22. dec 2002, 20:17

Tole naj bi bil tale algoritem.

Meni smrdi, odkar sem ga implementiral.

Man muss immer generalisieren - Carl Jacobi

Thomas :: 22. dec 2002, 20:30

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 :: 22. dec 2002, 21:01

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 (22. dec 2002 ob 21:07)

CHAOS :: 22. dec 2002, 21:15

Thomas: Kaj je to multibitna aritmetika oziroma kje lahko izvem kaj več o tem kako to narediti?

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

Thomas :: 22. dec 2002, 21:39

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 :: 22. dec 2002, 23:29

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 :: 23. dec 2002, 01:13

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 (23. dec 2002 ob 01:13)

Thomas :: 23. dec 2002, 01:34

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 :: 23. dec 2002, 03:11

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 :: 23. dec 2002, 08:25

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 :: 23. dec 2002, 09:23

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 :: 23. dec 2002, 09:27

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 :: 23. dec 2002, 09:47

Thomas:

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

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

0:)

fx :: 15. dec 2004, 22:23

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 :: 16. dec 2004, 00:12

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 :: 16. dec 2004, 00:18

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 (16. dec 2004 ob 00:19)

Arthur :: 16. dec 2004, 00:51

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 (16. dec 2004 ob 01:14)

Yacked2 :: 29. okt 2012, 16:57

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

Vredno ogleda ...

	Tema	Sporočila	Ogledi	Zadnje sporočilo
	Tema	Sporočila	Ogledi	Zadnje sporočilo
»	Python Redorange Oddelek: Programiranje	20	2931 (1617)	d_DJ 13. sep 2016 12:21:41
»	matematika-zaporedja (strani: 1 2 ) chrispy Oddelek: Šola	56	5976 (4812)	lebdim 23. okt 2014 22:52:23
»	Casovna kompleksnost algoritma bajsibajsi Oddelek: Programiranje	7	1327 (1082)	lebdim 24. feb 2014 22:47:04
»	Random Double_J Oddelek: Znanost in tehnologija	43	4400 (3630)	Thomas 17. sep 2003 12:10:39
»	Neskončno... (strani: 1 2 ) Yohan del Sud Oddelek: Loža	61	7289 (6203)	Gh0st 29. mar 2002 20:52:21

Več podobnih tem

Forum » Znanost in tehnologija » pra števila..

pra števila..

pra števila..

tx-z :: 19. dec 2002, 15:10

Thomas :: 19. dec 2002, 16:36

tx-z :: 19. dec 2002, 19:53

Gandalfar :: 19. dec 2002, 19:54

Thomas :: 20. dec 2002, 15:49

rsaver :: 20. dec 2002, 17:57

Thomas :: 20. dec 2002, 18:38

Thomas :: 20. dec 2002, 18:41

CHAOS :: 21. dec 2002, 22:10

Thomas :: 21. dec 2002, 22:22

Thomas :: 22. dec 2002, 19:49

Thomas :: 22. dec 2002, 20:17

Thomas :: 22. dec 2002, 20:30

Thomas :: 22. dec 2002, 21:01

CHAOS :: 22. dec 2002, 21:15

Thomas :: 22. dec 2002, 21:39

asPeteR :: 22. dec 2002, 23:29

Thomas :: 23. dec 2002, 01:13

Thomas :: 23. dec 2002, 01:34

CHAOS :: 23. dec 2002, 03:11

Thomas :: 23. dec 2002, 08:25

asPeteR :: 23. dec 2002, 09:23

Thomas :: 23. dec 2002, 09:27

asPeteR :: 23. dec 2002, 09:47

fx :: 15. dec 2004, 22:23

Arthur :: 16. dec 2004, 00:12

Primoz :: 16. dec 2004, 00:18

Arthur :: 16. dec 2004, 00:51

Yacked2 :: 29. okt 2012, 16:57

Vredno ogleda ...

matematika-zaporedja (strani: 1 2 )

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

Forum » Znanost in tehnologija »
pra števila..