Enrere Mòdul 3
Fonaments de Programació. Llenguatge C/C++---
Pràctica  Resum teòric Exercicis
Pràctica d'ampliació

 
Nombres primers

En aquesta pràctica presentarem també un algorisme senzill i conegut que permet saber si un nombre enter entrat per teclat és o no un nombre primer. 

 

Desenvolupament de la pràctica

Creeu un nou arxiu del tipus C anomenat m3p02.c i escriviu el següent codi:

//m3p02.c - Determinació de nombres primers  -

#include <stdio.h>

#include <stdlib.h>
#include<math.h>

int primer(int);

int main(){

    int num; 

    system("clear");

    printf("\t Introduïu el nombre>... ");
    scanf("%d",&num);

    if(primer(num)) printf("El nombre introduït és primer\n");

    else printf("El nombre introduït és compost\n");

    return 0;

}

 

int primer(int num) {

     //torna 1 si el nombre introduït num és primer 

     int lim,divisor=2;

 

    lim=int(sqrt(num));

    while(divisor<=lim){

        if(!(num%divisor)) return 0;

        divisor++;

    }

    return 1;

}

 

Captura de l'execució del programa.

 

 

Explicació del programa

Un nombre primer és un nombre que només es pot dividir entre 1 i entre ell mateix. La llista dels primers nombres primers és 1,2,3,5,7,11,13,17,...

El mètode que es fa servir en aquest programa per comprovar si un nombre és o no primer és fer la divisió entre tots els nombres més petits que la seva arrel quadrada i comprovar si la resta d'aquestes divisions és 0. ¿Per què l'arrel quadrada?. Evidentment, un  nombre no pot descompondre en factors tots els més grans que l'arrel quadrada d'aquest nombre.

En el programa s'ha definit una funció que torna un valor enter: 0 si l'argument és compost i 1 si l'argument és primer. La part principal de la funció és la següent:

 

    while(divisor=<lim){

        if(!(num%divisor)) return 0;

        divisor++;

    }

    return 1;

Fixeu-vos que en el cos del bucle hi ha una sentència if que comprova si la variable divisor és o no un divisor de num (Si en fos, l'expressió lògica !(num%divisor) seria vertadera i se sortiria de la funció amb el valor de retorn 0. Si se surt del bucle vol dir que s'ha provat tots els nombres més petits que l'arrel quadrada de num i no s'ha trobat cap divisor, en aquest cas, el valor de retorn serà 1.