Algoritm Numar Prim In C++

[Ovidiu29]

Acum cateva zile am facut un mic algoritm care sa spuna daca nr. e prim sau nu.

#include <iostream>

using namespace std;

int main()
{
    long int n;

    cout <<"n=";
    cin >>n;

    if(n%2>0 && n%3>0 && n%5>0 && n%7>0)
    cout <<"E prim."<<'n';
    else
    cout <<"Are divizori."<<'n';


    return 1;

}

[+GodsOtherHand]

esti sigur ca e bun?

[Courage]

Nop, nu e bun. In primul rand tu nu trebuie sa iei pe cazuri. Trebuie la general

 

Uite 2 variante:

 

1. (numaratul divizorilor)

#include <iostream>
using namespace std;
int main()
{
    int n,d,s=0;
    cout<<"n=";
    cin>>n;
    for (d=1;d<=n;d++)
        if (n%d==0)
            s++;
    if (s==2)
        cout<<"Este prim";
    else
        cout<<"Nu este prim";
    return 0;
}

2. 

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    unsigned n,d,OK;
    cout<<"n=";
    cin>>n;
    OK=1;
    if (n%2==0 and n!=2)
        OK=0;
    else
    {
        d=3;
        while (d<=sqrt(n) and OK==1)
            if (n%d==0)
                OK=0;
            else
                d=d+2;
    }
    if (OK==1)
        cout<<"numarul este prim";
    else
        cout<<"numarul nu este prim";
    return 0;
}

[hiey19]

@Courage:

Vezi ca e gresit la primul algoritm.In for mergi de la 1 la jumatatea numarului.Un nr prim ii are ca si divizori doar pe unu si pe el insusi.Daca tu verifici de la 1 la n/2 si s ajunge la 2 atunci tu vei avea 3 divizori nu 2.(cei 2 gasiti+numarul care nu intra in for pentru ca mergi pana la jumatate).Mai usor e sa initializezi suma cu 0.In for mergi de la 2 la jumatatea numarului.(tu stii ca 1 si n sunt deja divizori si nu vei gasi un divizor mai mare decat jumatatea numarului)Daca tu gasesti un divizor intre 2 si jumateatea numarului atunci nu mai e prim.(if(s==0) atunci nr prim else nu e prim)

 

Poti sa lasi si asa insa initializezi s cu 1.(pt n insusi) Numai forul il va verifica inutil pe 1 care stii ca e deja divizor.

[Courage]

Am editat. Credeam ca pusesem n, nu n/2 . 

[hiey19]

Nu e optimizat asa.Tu faci toate cazurile dintre n/2 si n aiurea+1 care stii deja ca e divizor. Daca ai un numar foarte mare atunci risipa e si mai mare. De acea ziceam sa faci intre 2 si n/2 si atunci if(s>0) => nr nu e prim.

[Courage]

Marog, 

#include <iostream>
using namespace std;
int main()
{
    int n,d,x=1;
    cin>>n;
    if (n==2)
        cout<<"Este prim";
    else
    {
        if (n%2==0)
            cout<<"Nu este prim";
        else
        {
            for (d=3;d<=n/2;d=d+2)
                if (n%d==0)
                    x=0;
            if (x==1)
                cout<<"Este prim";
            else
                cout<<"Nu este prim";
        }
    }
    return 0;
}

[hiey19]

Ai folosit x ca si un OK.Nu mai ai nevoie de s atunci.

 

O sa vezi mai tarziu cat de important e sa optimizezi un program.E bine sa te inveti cat mai repede.

[+GodsOtherHand]

Partea cu optimizarea depinde.. 

 

la un proiect mare, unde viteza nu e critica, e mult mai important un cod corect si usor de inteles, decat un cod optimizat, dar pe care nul intelege nimeni. 

[hiey19]

Toata lumea prefera o viteza mai buna.

Daca e usor sa-l optimizezi de ce sa nu o faci ? Ce rost are sa pui calculatorul sa faca o treaba inutila?

 

Da e adevarat ce zici tu insa se aplica la o alta forma de optimizare.(acolo unde trebuie sa-ti schimbi modul de abordare doar ca sa-l faci mai optim ,iar impactul nu e mare)

[+GodsOtherHand]

de exemplu uitate doar la diferenta de timp intre acelasi algoritm in java, si acelasi algoritm in C. Mai ales unul destul de complex. 

Desii ala in Java e mai scurt, mai usor de scris, mai usor de citit, ala din C va fi mult mai mic (ca si marime efectiva.. MB) si va rula mult mai repede.

 

Cat despre "Ce rost are sa pui calculatorul sa faca o treaba inutila?" ai facut POO? ai vazut cate chestii inutile pentru comp sunt? atatea obiecte care comunica intre ele, care apeleaza metode care nu fac io stiu ce..doar pentru ca sunt niste principii de urmat? acele principii sunt acolo pentru a face codul bun nu pentru comp, ci pentru oameni. 

 

 

Bine, acu vorbesc despre lucruri la cu totul alta scara Pav, fa codul cat mai optimizat. Acuma nici sa picam in cealalta extrema si sa facem chestii inutile nu e bine

[hiey19]

Totusi,trebuie sa invete sa lucreze eficient. Spre exemplu la olimpiada ai o marja de timp in care sa se incadreze programul , poti sa-l faci tu super ok ,dar daca nu e optimizat si nu lucreaza la acel nivel nu primesti nimic.(bine... am vazut ca in ultimul timp intervalul de timp nu cauzeaza probleme)

 

Sa ramanem la chestia esentiala : daca intelegi programul si stii cum sa-l optimizezi usor , optimizeaza-l.

[Ovidiu29]

Multumesc pentru sfaturi! O sa le urmez.

[Courage]

E mai OK cel de mai jos?

#include <stdio.h>
#include <math.h>
int main()
{
    int n,d,x=1;
    scanf("%d", &n);
    if (n==2)
        printf("Este prim");
    else
    {
        if (n%2==0) // Eliminat situatiile cand este par si nu egal cu 2
            printf("Nu este prim");
        else
        {
            for (d=3;d<=sqrt(n);d=d+2)
                if (n%d==0)
                {
                    printf("Nu este prim");
                    break; //Daca deja am gasit un divizor propriu afisez ca nu e prim si opresc procesul
                    x=0;
                }
            if (x==1)
                printf("Este prim");
        }
    }
    return 0;
}

[hiey19]

Ar putea fi mai ok pentru ca verifici mai putine cazuri decat cu un for(cel de la 2 la jumatatea nr.) ,dar nu-si are rostul.E prea lung pentru un lucru atat de mic. Si nu prea e elagant cu break.