Question

Nume problema: prim002
Sursa: pbinfo.ro
Cerința
Anul 2017 tocmai s-a încheiat, iar nostalgicii suferă în tăcere deoarece acesta era număr prim. Dorel, un personaj întreprinzător, s-a gândit să afle pentru un număr natural n dat, care este cel mai mare divizor prim al acestuia.

Date de intrare
Programul citește de la tastatură numărul n.

Date de ieșire
Programul va afișa pe ecran cel mai mare divizor prim al lui n.

Restricții și precizări
1 ≤ n ≤ 10 la 14

Exemplu
Intrare

2018
Ieșire

1009
Explicație
Divizorii lui 2018 sunt 1, 2, 1009, 2108, iar cel mai mare divizor prim este 1009.
Indicatii:
Se află divizorii lui n şi se verifică dacă sunt numere prime.
PS: am facut acest lucru si am primit limita de timp depasita.

Am lucrat ceva vreme la problema si am reusit 80 puncte dar imi tot scapa cazul 7 si cazul 8. Aceste cazuri nu sunt specificate.

Acesta este programul meu:

#include <iostream>
#include <cmath>
using namespace std;
int eprim(int x)
{    if(x==0 || x==1)       
return 0;   
if(x==2)       
return 1;   
if(x%2==0)       
return 0;   
for(int d=3;d*d<=x;d++)       
if(x%d==0)       
return 0;   
 return 1;
}
int main()
{    long long int n,d,s=0,nr1=0,nr2=0;   
cin>>n;   
if(n==1)       
cout<<0;   
else   
if(eprim(n))       
cout<<n;   
else   
{       
for(d=2;d*d<n;d++)   
{       
if(n%d==0)       
{           
if(eprim(d))           
{               
nr1=d;           
}           
if(eprim(n/d))           
{               
nr2=n/d;               
d=n;           
}       
}   
}   
if(d*d==n && eprim(d))       
cout<<d;   
else   
if(nr1>nr2)       
cout<<nr1;   
else       
if(nr2>nr1)           
cout<<nr2;       
else           
cout<<n;   
}
return 0;
}

Answer 1

Problema se abordeaza diferit. Este suficient sa faci o descompunere in factori primi.

#include <iostream>
using namespace std;

int main() {
    long long n, max = 0, d = 2;
    cin >> n;
    while(d * d <= n) {
        if(n % d == 0) {
          while(n % d == 0)
            n /= d;
          if(d > max)
            max = d;
        }
        d++;
    }
    if(n > 1)
      max = n;
    cout << max; 
    return 0;
}