Exerciţii C++ Numere Prime

[Courage]

1. Program care afişează dacă un număr citit de la tastatură este prim sau nu

2. Citindu-se un interval [a,b], se va afişa câte numere prime se află în acel interval

3. Cel mai mare număr prim, mai mic decât numărul n, citit de la tastatură

4. Cel mai mic număr prim, mai mare decât numărul n, citit de la tastatură

 

1.

#include <stdio.h>
#include <math.h>
int main(void)
{
    int n,d,ok;
    scanf("%d",&n);
    if (n%2==0)
    {
        if (n==2)
            printf("Este prim");
        else
            printf("Nu este prim");
    }
    else
    {
        ok=0;
        d=3;
        while (ok==0 && d<=sqrt(n))
        {
            if (n%d==0)
                ok=1;
            d=d+2;
        }
        if (ok==0)
            printf("Este prim");
        else
            printf("Nu este prim");
    }
    return 0;
}

2.

#include <stdio.h>
#include <math.h>
int main(void)
{
    int a,b,i,n,d,ok,s=0;
    scanf("%d %d",&a,&b);
    for (i=a;i<=b;i++)
    {
        if (i%2==0)
        {
            if (i==2)
                s++;
        }
        else
        {
            ok=0;
            d=3;
            while (ok==0 && d<=sqrt(i))
            {
                if (i%d==0)
                    ok=1;
                d=d+2;
            }
            if (ok==0)
                s++;
        }
    }
    printf("%d",s);
    return 0;
}

3.

#include <stdio.h>
#include <math.h>
int main(void)
{
    int n,x,ok=1,d,ok1;
    scanf("%d",&n);
    x=n;
    if (x%2==0)
        x=n+1;
    while (ok)
    {
        x=x-2;
        ok1=0;
        d=3;
        while (ok1==0 && d<=sqrt(x))
        {
            if (x%d==0)
                ok1=1;
            d=d+2;
        }
        if (ok1==0)
        {
            printf("%d",x);
            ok=0;
        }
    }
    return 0;
}

4.

#include <stdio.h>
#include <math.h>
int main(void)
{
    int n,x,ok=1,d;
    scanf("%d",&n);
    x=n;
    if (x%2==0)
        x=n-1;
    while (ok)
    {
        x=x+2;
        ok=0;
        d=3;
        while (ok==0 && d<=sqrt(x))
        {
            if (x%d==0)
                ok=1;
            d=d+2;
        }
        if (ok==0)
        {
            printf("%d",x);
            ok=0;
        }
    }
    return 0;
}

[ldd.man25]

Am ajuns la lectia cu "Algoritmi de divizibilitate", numere prime si alea alea

"Scrieti un program care sa afiseze descompunerea in factori primi ai unui nr natural n citit de la tastatura"

 

Ce am scris eu in caiet: "Caut divizori pornind de la 2 in sus, pt fiecare divizor gasit calculam ordinul de multiplicitate impartind succesiv pe n la divizor si calculand numarul de impartiri efectuate. Dupa care afisam atat divizorul gasit, cat si multiplicitatea sa. Procedeul se repeta cat timp numarul mai poate avea divizori. (cat timp nr!=0)."

 

Acum ca citesc a 2-a oara, nu prea mai inteleg atat de bn .

#include <iostream>
using namespace std;
int main()
{
 int n,i=2,k=0;
 cout<<"Introduceti numarul:";cin>>n;
while(n!=0) 
{ 
 while(n%i==0){k++;n=n/i;}
}

return 0; 
}

De aici nu mai stiu cum sa fac, as prefera o explicatie cum se face, ca sa il pot termina eu, nu sa primesc programul pe tava. Multumesc!

Nu injurati de acoladele de la primul while, ma gandeam ca poate mai umplu cu ceva intre timp

[Courage]

#include <iostream>
using namespace std;
int main()
{
    int n,d=2,p; // Nu prea are rost sa iei p=0 de aici, deoarece il initializezi cu 0 in interiorul while-ului
    cin>>n;
    while(n!=1) // Tot imparti numarul citit pana devine 1
    {
        p=0;
        while(n%d==0) 
        {
            /*
            Imparti n la d pana nu se mai divide, si aduni prin p de cate ori s-a putut imprati
            */
            p++;
            n=n/d;
        }
        if(p!=0) /* Verifici daca s-a impartit la d cel putin o data */
            cout<<d<<" la puterea "<<p<<endl;
        d++; /* Maresti d cu o unitate, deoarece numarul n nu mai este divizibil cu d-ul vechi */
    }
    return 0;
}

[ldd.man25]

Sau, alta formulare la acest programel: 

#include<iostream>
using namespace std;
int main()
{
    unsigned n,d=2,p;
    cin>>n;
    while(n!=1)
    {
        if(n%d==0)
        {
            p=0;
            while(n%d==0){p++;n=n/d;}
            cout<<d<<"^"<<p<<endl;
        }
        d++;
    }
    return 0;
}

[ldd.man25]

Intre timp am mai facut niste programe cu numere prime, la care nu am avut nevoie de ajutor si de voi posta cand consider ca am timp.

Acum am ajuns la algoritmul pt determinarea numerelor prime.

//Algoritm pt determinarea numerelor prime.
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    int n,i,k=1;
    cout<<"Introduceti numarul: ";cin>>n;
    for(i=2;i<=sqrt(n);i++)
    if(n%i==0){k=0;i=n;}
    if(k!=0)cout<<"Nr prim.";
    else cout<<"Numarul nu este prim.";

    return 0;
}

Primul exercitiu dupa acesta a fost "se citest n de la tastatura, sa se afiseze toate numerele prime pana la acel nr citit", asta am facu singur.

Al doilea: se citeste un nr nat n, sa se afiseze primele n numere naturale prime. Exemplu: se citeste 4, afisare 2,3,5,7.

Nu prea am idei la asta, stiu ca trebuie cu un while sau do while, dar nu stiu ce conditii sa pun. Niste idei ar fi de ajutor, multumesc.

[Courage]

Pai, hmm. Ca sa intelegi mai bine, iei un i=1 si s=0. Citesti n, si tot ii cresti valoarea lui i. Cand i este prim, lui s ii mai adaugi o unitate, si tot asa pana devine egal cu n.

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    int n,s=0,i,d,ok;
    cout<<"n=";
    cin>>n;
    i=0;
    while (s!=n) // nu bag s<=n deoarece imi mai afiseaza un numar prim in plus decat ar trebui
    {
        i++;
        /* Aici verificam daca este prim */
        if (i%2==0)
        {
            if (i==2)
            {
                cout<<"2 ";
                s++;
            }
        }
        else
        {
            ok=true;
            d=3;
            while (d<=sqrt(i) and ok)
                if (i%d==0)
                    ok=false;
                else
                    d=d+2;
            if (ok)
            {
                cout<<i<<" ";
                s++;
            }
        }
    }
    return 0;
}

[ldd.man25]

Ce inseamna ok=true si "and-ul" folosit in primul for? Gen &&ok!=0 ?

[+Raziel]

Asta numai programare structurata nu e... initializati variabilele in bloc separat, nu oriunde in sursa. Au scos astia Pascal din scoli ?

[Courage]

Ce inseamna ok=true si "and-ul" folosit in primul for? Gen &&ok!=0 ?

 

and = &&

in c/c++ false are valoarea 0, deci if(ok) e aceeasi chestie cu if(ok!=0) de exemplu.

[ldd.man25]

Asta numai programare structurata nu e... initializati variabilele in bloc separat, nu oriunde in sursa. Au scos astia Pascal din scoli ?

 

Cum adica "bloc separat"? Si de ce crezi ca nu a structurata?  Nu am facut Pascal deloc pana acum, totusi am vazut programul instalat in calculatoarele liceului. 

 

Courage, merci pentru ajutor.

 

[extraterestrial]

Se Citeste Un Nr. Natural De La Tastatura Cu Cel Mult 6 Cifre.sa Se Scrie Un Program Care Sa Afiseze Cel Mai Mare Divizor Comun Dintre Cifrele Acestui Numar.

#include<iostream>

using namespace std;

int main()

{

    unsigned n,i,c,x;

    cout<<"Dati un numar de maxim 6 cifre";

    do{cin>>n>>i=o;

    while(n!=0) {i=i+1;n=n/10;} }

    while(i>6) 

}

 

Pana aici am stiu sa fac, cum fac mai departe,daca se poate si niste explicatii ca sa il inteleg?

[Courage]

Pai, daca ai n = abcdef (cu bara deasupra), faci cmmdc intre numerele e si f, dupa care faci cmmdc intre numerele e si celelalte cifre ale numarului.

Nu cred ca e cel mai bun algoritm cel de mai jos, dar mie imi afiseaza cum trebuie.

#include <iostream>
using namespace std;
int main()
{
    int a,b,n;
    cin >> n;
    a = n%10;
    b = n/10%10;
    n = n / 100;
    while (a!=b)
        if (a>b)
            a-=b;
        else
            b-=a;
    while (n>0)
    {
        b=n%10;
        while (a!=b)
        if (a>b)
            a-=b;
        else
            b-=a;
        n/=10;
    }
    cout << a;
    return 0;
}

[extraterestrial]

Mersi