UVA 11466 - Largest Prime Divisor

UVA Sep 01, 2020

Problem PDF

Solution:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long
#define sc scanf
#define pf printf
#define pi 2*acos(0.0)

#define ft first
#define se second
#define Max 10001000
#define st(s) s.size();
#define r(input) freopen("input.txt","r",stdin)
#define w(output) freopen("output.txt","w",stdout)
#define maxall(v) *max_element(v.begin(),v.end())
#define minall(v) *min_element(v.begin(),v.end())
#define Sort(v) sort(v.begin(),v.end())
#define un(v) Sort(v), v.erase(unique(v.begin(),v.end()),v.end())
#define cover(a,d) memset(a,d,sizeof(a))
using namespace std;

bool prime[Max];
ll p[1000000],k=0;
void sieve()
{
	ll i,j;
	prime[1]=false;
	for(i=2;i<=10001000;i++)
	{
		if(prime[i]!=false)
		{
			p[k++]=i;
			for(j=i+i;j<=10001000;j+=i)
			{
				prime[j]=false;
			}
		}
	}
}
int main()
{
    cover(prime,true);
    sieve();
    ll n,i,j,a;
    int c;
    while(scanf("%lld",&n)==1)
    {
        if(n==0) break;
        if(n<0) n*=-1;
        for(i=0,c=0;i1&&p[i]<=n;i++)
        {
            if(n%p[i]==0)
            {
                //pf("%lld\n",p[i]);
                c++;
                while(n>1 && n%p[i]==0)
                {
                    n/=p[i];
                }
                a=p[i];
            }
            if(n==1) break;
        }
        if(n==1)
        {
            if(c>1) printf("%lld\n",a);
            else printf("-1\n");
        }
        else
        {
            if(c>0) printf("%lld\n",n);
            else printf("-1\n");
        }
    }
}

/*input
    1000
    20
    32
    1
    -1
    -10
    61536575712
    8172385155
    90090
    12
    199900
    -26356
    -32
    8748234
    23462482
    23457826407
    234872648001
    436598
    345387
    2347
    17
    37
    0

output:
    5
    5
    -1
    -1
    -1
    5
    324889
    16509869
    13
    3
    1999
    599
    -1
    113
    690073
    77418569
    348559
    521
    16447
    -1
    -1
    -1
*/
https://github.com/Shipu/OnlineJudgeProblemSolutionWithCPlusPlus/tree/master/uva/11466/11466.cpp

Tags

Shipu Ahamed

CSPO® | Partly Product, Project Manager and Partly Software Engineer.

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.