11466 - Largest Prime Divisor

[roger12345]

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

Code: Select all

AC NOW

EDIT: My sieve was too slow

[shaon_cse_cu08]

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

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;
}

[PromeNabid]

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]

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]

Doesn't match the sample I/O.

[?????? ????]

Code: Select all

Remove After Accepted

[alimbubt]

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

[walking_hell]

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]

Input 4 output should be -1

[ashdboss]

getting wrong answer. need help
removed after getting accepted

[t.tahasin]

Input:
-21
-22
0

Output:
7
11

[ashdboss]

Thanks...got AC

[saniatrasel]

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]

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]

Input

Code: Select all

9
0

Correct output

Code: Select all

-1