[c++]stora primtal

lite tips är att ett jämnt tal aldrig kan vara ett primtal då det är delbart med 2. För att halvera tiden kan du bara söka med de talen under hälften av talet då ena faktorn av talet ligger här.

Hur kollar man om en variabel innehåller ett heltal eller ett decimaltal?

I C++ då..

EDIT :

Haha! Ojojoj, skratta ordentligt nu.

Här kommer min uberfulkodslösning på det problemet.

#include <iostream.h>

int main() {



int heltal;
float flyttal;
float flytttalcpy;
int prim;

flyttal %= prim;

flyttalcpy=flyttal;

flyttal=heltal;

if (flyttalcpy!=heltal) {

cout << "bleep" << endl;

return 0;

}


else 

{

cout << "successssssss" << endl;

return 0;

}

}

Hmm, kom fram till att flyttal=heltal; kanske inte kommer överens med kompilatorn så bra.

Men jag har tyvärr ingen kompilator här att testa det med.

Hur menar du egentligen?.. C/C++ har ju speciella flyttal/heltalstyper .. en int/short/long kan ju inte innehålla ett flyttal. Vill du veta om ett flyttal egentligen är ett heltal eller vadå? ..

[EDIT] carls: .. posta gära en fungerande lösning .. t.ex. så kan man inte använda % pål flyttal ..

Jag vill t.ex, ta ett tal och dela det med ett annat. Sen vill jag veta om det blev ett decimaltal eller ett heltal och om det blev ett heltal drar jag t.ex. en i++ och annars ingenting. Fattar du?

EDIT : Jag menar, en float kan ju innehålla 1.000000 också..

if((tal1 % tal2) == 0)
{
// ingen rest vid divisionen ..
}
else
{
// rest vid divisionen ..
}

Huh?

EDIT : Läste på msdn om den där grunkan nu. Så nu fattar jag.

eh .. kan du inget om modulus eller?

Läs edit.

Var ett väldans flängade mellan inläggen här.

EDIT : Så här menade jag.

#include <iostream.h>

int main() {



int heltal;
float flyttal;
float flytttalcpy;
int prim;
flyttal=flyttsplit:
flyttal = flyttsplit / prim;

flyttalcpy=flyttal;

flyttal=heltal;

if (flyttalcpy!=heltal) {

cout << "bleep" << endl;

return 0;

}


else 

{

cout << "successssssss" << endl;

return 0;

}

}

Min lösning:

bool isPrime(int tal) {
	int sq = sqrt(tal);
	bool prime = 1;
	
	// testa att dividera tal med alla primtal som är mindre än sqrt(tal)
	char* primes = new char[sq];
	memset(primes, 1, sq);
	for(int n=2;n<=sq;n++) {
		if(primes[n-1] == 0)
			continue;

		if(tal%n == 0) {
			prime = 0;
			break;
		}

		for(int i=n+n; i<=sq; i+=n)
			primes[i-1] = 0;

	}

	delete primes;
	return prime;
}

EDIT: benchade lite. Den tog 10000 tal (talet 999999937) på 8,8 sekunder. Jag har en AMD mobile på 796mhz.

         if(tal1%2==0)
             k=1;
         if(k==0)
             for(i=tal1/2-1;i>=4;i--)
                 if(tal1%i==0)
                        k=1;
         if(k==1)
              cout<<tal1<<" är inte ett primtal\n";
         else
              cout<<tal1<<" är ett primtal\n";

Dessa rader borde räcka, dock kommer det att ta lång tid vid höga tal som 10^9 så länge de är ojämna

http://forum.sweclockers.com/showthread.php?s=&threadid=46869...
Psionicist är väl den som e snabbast, dock så får man kolla vilken säkerhet man vill ha på sina primatal först..

Erastotenes (?) såll ska vara bra om man ska hitta alla primtal under ett visst maxvärde, använd det en bit, sen utnyttjar du att produkten av alla primtal under ett visst värde plus 1 också är ett primtal, ex:
2*3*5 + 1 = 31
2*3*5*7 + 1 = 211
Borde gå ganska snabbt.

edit: jag måste minnas fel, det gäller tydligen inte alltid, 2*3*5*7*11*13+1 är inte ett primtal

Kanske du blandar ihop det med att alla tal som ej är primtal kan delas upp i multiplar av primtal, Thurén?

säg.. 30 som öppenbart ej är ett primtal,
2*3*5=30

edit: Förresten så rekommenderar jag att du använder
http://www.faust.fr.bw.schule.de/mhb/eratosiv.htm

Använd ett primtalstest (typ Rabin-miller) istället. Kombinera gärna flera test.

Thurén: produkten av t ex 2*3*5*7*11*13+1 är bara garanterat att inte innehålla någon av faktorerna 2,3,5,7,11 eller 13 (för om man försöker dela med något av dem får man ju resten 1).

Rabin-miller känns som lite overkill eftersom talen han snackade om inte var större än ca 10^9. Rabin-miller är ju inte ett säkert test heller utan måste kombineras med andra för att vara säkert, dock extremt snabbt. Kraven var också låga, under 1 sekund. Följande kod instantierad med en unsigned long int körs på min burk på under en millisekund (förmodligen mycket snabbare, orkade inte testa antal klockcykler, finaste upplösningen på systemklockan är ju 1 ms) när talet man testar ligger i storleksområdet 10^9.

template<class int_compatible>
bool is_prime(int_compatible n)
{
  int_compatible x = -1;
  int_compatible y = 0;
  if (n == 3) return true;
  if (n == 2) return true;
  if (n == 1) return false;
  if ((n % 2) == 0) return false;
  while (((x*x) < n) && (y < 2))
    {
      x=x+2;
      if ((n % x) == 0) y++;
    }
  if (y != 1) return false;
  else return true;
}

Sök primtal:
Per definition är primtal heltal, heltal som enbart delas jämt av sig själv och 1.
1 är inget primtal, således är 2 det första primtalet.

Det finns två vägar man kan gå för att verifiera om ett tal är ett primtal:
1. att verkligen pröva om talet är ett primtal
2. att nyttja en sannolikhetsmodell

för att implementera 1:an, vilket är enklast, så räcker det att undersöka om att talet två samt varje udda heltal större än ett men mindre än roten ur det tal man undersöker INTE delar det givna talet.

för att implementera 2:an så får man tänka efter vad för noggranhet man kräver.
Detta kommer återspegla sig i hur måga test man gör med talet.
De vanligaste testen man gör är Rabin-Miller Strong Pseudoprime Test, ECM (Elliptic Curve Method) eller(samma sak under annat namn) Elliptic Curve Primality Proving samt Lucas-Lehmer Test
"All" teori bakom dessa test kan du finna antingen med google eller dra direkt till http://mathworld.wolfram.com

Fördelen med 2:an jämfört med 1:an är att 2:an går så sjukt mycket snabbare för tal större än låt oss säga 10^20
Inom den region du söker primtal (storleksordningen 10^9 förutsatt att det inte är 10^9 siffror du menar...) så rekomenderar jag dig att implementera 1:an

Erastotenes såll går ut på att man skriver upp alla tal under ett visst värde och sedan delar man alla med 2,3,4.... och tar bort de talen som det går jämnt upp med så det hade nog varit lite jobbigt när man ska räkna så många tal

Att han skulle använda Erastotenes byggde givetvis på att produkten av primtalen plus ett också var ett primtal, isf hade det gått snabbt som tusan.

Eratosthenes hette gubben! Men även om det där funkat så förstår jag inte vad du skulle ha det till. Det är meningslöst om man vill hitta alla primtal eller bestämma om ett speciellt tal är ett primtal. Produkten av alla primtal växer exponentiellt, så du kommer missa massvis av primtal. Här är de första 20 produkterna:

2
3
7
31
211
2311
30031
510511
9699691
223092871
6469693231
200560490131
7420738134811
304250263527211
13082761331670031
614889782588491411
32589158477190044731
1922760350154212639071
117288381359406970983271
7858321551080267055879091
557940830126698960967415391