Definíció:

Azokat a számokat, amelyeknek nincs valódi osztójuk, törzsszámoknak vagy prímszámoknak, azokat pedig, amelyeknek van valódi osztójuk, összetett számoknak nevezzük.

Az 1-et nem soroljuk sem a törzs-, sem az összetett számok közé.

Prim tényezőkre bontás

Az összetett szám összes osztójának meghatározását elősegíti a törzsszámosztók ismerete. Ezeket törzstényezőknek nevezzük. Minden természetes szám egyértelműen felbontható törzstényezőire. Ezt a törzstényezőkre bontást úgy végezhetjük el, hogy az adott számot elosztjuk a legkisebb törzsszámmal, amelyik a számnak osztója. A hányadost ismét elosztjuk a benne található legkisebb törzsszámmal, és azt addig ismételjük, amig a hányados egy lesz. Az így kapott törzsszámok az adott szám törzstényezői.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

int Prim(int);

int KovPrim(int);

int main()

{

int n,d=2;

printf("Vizsgalando szam:");

scanf("%d",&n);

printf("Prim felbontas:\n");

while(!Prim(n))

{

while(1)

{

if(n%d==0)

{

printf("%d\n",d);

n/=d;

break;

}

d=KovPrim(d);

}

printf("%d",n);

getchar();

printf("\n");

system("PAUSE");

}

int Prim(int n)

{

int i;

for(i=2;i<=n/2;i++)

{

if(n%i==0)

return 0;

}

return 1;

}

int KovPrim(int n)

{

if(n==2)

n++;

else

n+=2;

}

while(!Prim(n));

return n;

}