11466 - Largest Prime Divisor

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

roger12345
New poster
Posts: 3
Joined: Tue Feb 01, 2011 5:40 am

Re: 11466 - Largest Prime Divisor

Post by roger12345 » Thu Jun 16, 2011 7:45 pm

Help me please im gettins time limit, the input 99999999999997 doesnt finish :S

Code: Select all

AC NOW
EDIT: My sieve was too slow

User avatar
shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

Re: 11466 - Largest Prime Divisor

Post by shaon_cse_cu08 » Tue Nov 08, 2011 7:52 pm

I use my own prime factorization function... this is Child's math... divide a number a number until it can't be divided... dan increment it by 2..bcoz all primes except for 2 are odd... and my code gave me 0.032 s... It would b more faster if i use only da prime... but sometimes Simplicity is more fun dan complexity :D

Code: Select all

#include<stdio.h>
int main()
{
	int i,n;

	while(scanf("%d",&n)!=EOF)
	{
		while(n%2==0)
		{
			printf("2 ");
			n/=2;
		}
	
		for(i=3;i*i<=n;)
		{
	 		if(n%i==0)
			{
				n=n/i;
				printf("%d ",i);
			}
			else
				i+=2;
		}
		if(n>1)
			printf("%d\n",n);
	}
return 0;
}
I'll keep holding on...Until the walls come tumbling down...And freedom is all around ..... :x

PromeNabid
New poster
Posts: 21
Joined: Mon Jun 18, 2012 12:52 am
Location: Dhaka, Bangladesh.
Contact:

Re: 11466 - Largest Prime Divisor

Post by PromeNabid » Sat Jun 30, 2012 1:02 am

Some sample I/O for this problem.
Input:

Code: Select all

1
-1
1111111111111
12345678910121
12345678910121
1234567891012
99999999999997
0
Output:

Code: Select all

-1
-1
265371653
173882801551
173882801551
4281283
119189511323

masri77
New poster
Posts: 1
Joined: Wed Jul 18, 2012 3:32 am

Re: 11466 - Largest Prime Divisor

Post by masri77 » Wed Jul 18, 2012 3:35 am

The program generates correct output but gets WA please help ..

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
	long long int num, ans;
	long long int i;

	while (scanf("%lld", &num) && num != 0) {
		if (num < 0)
			num *= -1;

		ans = num;

		while (ans % 2 == 0)
			ans /= 2;

		i = 3;
		while (i * i <= ans) {
			if (ans % i == 0)
				ans /= i;
			else
				i += 2;
		}
		printf("%lld\n", num == ans ? -1 : ans);
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11466 - Largest Prime Divisor

Post by brianfry713 » Thu Jul 19, 2012 3:08 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

?????? ????
New poster
Posts: 7
Joined: Tue Apr 03, 2012 2:34 pm
Location: Manikgonj, Bangladesh

Re: 11466 - Largest Prime Divisor

Post by ?????? ???? » Mon Oct 08, 2012 1:25 pm

Code: Select all

Remove After Accepted

alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Location: BUBT,Dhaka, Bangladesh
Contact:

Re: 11466 - Largest Prime Divisor

Post by alimbubt » Mon Apr 08, 2013 4:19 am

For this problem, Some important notes are...
1) What will happen when there exists less than 2 prime divisors.
2) What will happen when the input is less than 0.

Some Input-Output:
Input:

Code: Select all

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

Code: Select all

5
5
-1
-1
-1
5
324889
16509869
13
3
1999
599
-1
113
690073
77418569
348559
521
16447
-1
-1
-1
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/

walking_hell
New poster
Posts: 14
Joined: Tue Sep 24, 2013 4:35 pm

uva 11466

Post by walking_hell » Fri Nov 29, 2013 5:45 pm

cant find my bug !!!

Code: Select all

#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#define max 10000500
using namespace std;
vector <long long> prime;
bool flag[max];

void sieve()
{

    prime.push_back(2);
    //cout<<"h;;";
    for(long long i=4;i<max;i+=2)
    flag[i]=true;
    for(long long i=3;i<max;i+=2)
    {
        if(!flag[i])
        {
            prime.push_back(i);
            if(max/i>=i)
            {
                int add=i*2;
                for(long long j=i*i;j<max;j+=add)
                flag[j]=true;
            }


        }
    }

}
int main()
{
    long long x;
    sieve();
    while(cin>>x && x)
    {
        long long m=x;
        if(x<0)
        x=-x;
        long long int flag=0,dlx=0;
        for(int i=0;prime[i]<max;i++)
        {


            flag=0;
            while(x%prime[i]==0)
            {
                x=x/prime[i];
                if(prime[i]>dlx)
                dlx=prime[i];
            }
            for(long long l=i;prime[l]<=(long long)sqrt(x);l++)
            {
                if(x%prime[l]==0)
                {
                    flag=2;
                    i=l-1;
                    break;

                }



            }
            if(flag==0)
            {
                if(x>dlx)
                dlx=x;
                break;

            }


        }
        if(dlx==0 || dlx==m)
        cout<<"-1"<<endl;
        else
        cout<<dlx<<endl;


    }

    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: uva 11466

Post by brianfry713 » Tue Dec 03, 2013 1:38 am

Input 4 output should be -1
Check input and AC output for thousands of problems on uDebug!

ashdboss
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

uva 11466

Post by ashdboss » Tue Dec 10, 2013 10:57 am

getting wrong answer. need help
removed after getting accepted
Last edited by ashdboss on Tue Dec 10, 2013 2:50 pm, edited 1 time in total.

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

Re: uva 11466

Post by t.tahasin » Tue Dec 10, 2013 2:43 pm

Input:
-21
-22
0

Output:
7
11

ashdboss
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

Re: uva 11466

Post by ashdboss » Tue Dec 10, 2013 2:49 pm

Thanks...got AC :)

saniatrasel
New poster
Posts: 5
Joined: Tue Apr 07, 2015 11:10 am

Re: 11466 - Largest Prime Divisor

Post by saniatrasel » Tue Apr 07, 2015 11:17 am

I get WA of the below code... Though all sample inputs are successfully generate desired output.
But still I get WA from UVa. Here is the below code:

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
	long long num;
	int count = 0;
	while((scanf("%lld",&num))&&(num!=0))
	{
		long long int i;
		count = 0;
		if(num<0)
			num = num *-1;
		for(i=2;i<=sqrt((double)num);i++)
			{				
				while((num%i==0)&&(i!=num))
				{
					num = num/i;
					count++;
				}			
				if(num<i)
					break;
			}
			if(count>0)				
				printf("%lld\n",num);				
			else			
				printf("%d\n",-1);		
	}
}

papon sen
New poster
Posts: 1
Joined: Mon Nov 16, 2015 9:39 pm

Re: 11466 - Largest Prime Divisor

Post by papon sen » Sat Dec 26, 2015 8:28 am

The program generates correct output but gets wrong ans. I tried it for each input which is given.Please help me to find why my code is getting wrong answer.

Code: Select all

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,input;
    while(scanf("%lld",&input)!=EOF)
    {

        if(input==0)
            break;
        if(input<0)
            input*=(-1);
        n=input;
        long long int counter=2;
        long long int largest;
        while(counter*counter<=n)
        {

            if(n%counter==0)
            {
                n=n/counter;
                largest=counter;
            }
            else{
                    if(counter==2)
                        counter=3;
                    else
                        counter+=2;

            }
        }
        if(n>=counter)
        {
            largest=n;
        }
        if(largest==2 || largest==input||input==1)
        {
            largest=-1;
        }
        printf("%lld\n",largest);
    }
    return 0;
}

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11466 - Largest Prime Divisor

Post by lighted » Fri Mar 10, 2017 2:07 pm

Input

Code: Select all

9
0
Correct output

Code: Select all

-1
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 114 (11400-11499)”