Jump to content

Algoritm Numar Prim In C++


Ovidiu29

Recommended Posts

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;

}

Respecta si vei fi respectat.

Link to comment
Share on other sites

  • Moderators

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;
}
Link to comment
Share on other sites

@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.

Link to comment
Share on other sites

  • Moderators

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;
}
Link to comment
Share on other sites

Toata lumea prefera o viteza mai buna. :)

Daca e usor sa-l optimizezi de ce sa nu o faci ?:P 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)

Link to comment
Share on other sites

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 :))

love is a verb
Love is a doing word

Link to comment
Share on other sites

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. :P

Link to comment
Share on other sites

  • 4 weeks later...
  • Moderators

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;
}
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.