Page 1 of 1

11408 - Count DePrimes

Posted: Mon Mar 31, 2008 9:26 pm
by turcse143
here is my code i got TLE.
I don't know whats my problem.
i use sieve for calculating the primes.
ples help.

Code: Select all

#include<stdio.h>
#include<math.h>
char Array[5000000];
int prime[200000];

void primes()
{
	int i,j,sN;
	sN = sqrt(5000000);
	for(i=2;i<=5000000;i++)
	{
		Array[i]='P';
	}
	for(i=2;i<sN;i++)
	{
		if(Array[i]=='P')
		{
			for(j=i*i;j<=5000000;j+=i )
			{
				Array[j]='C';
			}
		}
	}
}
int factor(int n) 
{ 
	int sum,mul,i;
	sum=0;mul=1;
	if(n%2==0)
	{
		sum+=2;
	}
	for(i=3;i<=n;i+=2)
	{
		if(Array[i]=='P'&&n%i==0)
		{
			sum+=i;
		}
	}
	return sum;
}

main()
{
	int i,a,m,n,count;
	primes();
	freopen("11408.in","rt",stdin);
	while(scanf("%d %d",&n,&m)==2)
	{
		if(n==0)
			break;
		count=0;
		for(i=n;i<=m;i++)
		{
			a=factor(i);
			if(Array[a]=='P')
				count++;
		}
		printf("%d\n",count);
		count=0;
	}
}

Re: 11408,deprimes i got TLE WHATS my problem

Posted: Tue Apr 01, 2008 10:41 pm
by fidels
It looks like you're trying to calculate everything on-place for each execution, which can be quite time-consuming. Try to input "2 5000000" and see if it takes a considerable amount of time (one that you can notice when running the program). If it does, then the TLE is due to this fact, and you should try another approach, such as precalculating values for some specific intervals...

EDIT: I compiled your program and it is much too slow for the 3 seconds you're given... try "2 100000" and see how long it takes!

Re: 11408 - Count DePrimes

Posted: Wed Apr 02, 2008 4:17 am
by sclo
There a few problems with the code. I can definitely tell that it is TLE even without running the code.

First factor(n) is too slow for 3 secs. Why not use the information in the sieve to help you factor? If you coded it correctly, factoring n can be done using O(k) operations for each n, where k is the number of prime factors of n.

Second, trying to sum all of the factors every time you compute an answer is also too slow. You need to use a culminative sum to allow you to answer the query in O(1) time.

Count DePrimes TL

Posted: Fri Apr 18, 2008 7:19 am
by ChiperOrtizII
Hi!! How Is EveryThing.... I Did Not Send It Yet Cause I Know TL Will Be Given... Takes 18 Seg in my Computer Memorazing 0..5000000 Solution....

Please Some Other Approach== Thanks In Advance I Am New In This... :D :D :D :D :D :D :D

Cristian Ortiz Venezuela

Code: Select all

import java.io.*;
import java.util.*;
public class Main
{
    static final int Max   = 5000000;
    static boolean Final[] = new boolean[Max+1];
    static boolean Vec[]   = new boolean[Max+1];
    static int Pri[]       = new int[348513];
    static Hashtable<Integer,Integer> Hash;
    static void Sieve(int L, int U)
    {
        for (int i=L;i*i<=U;i++)
            if (!Vec[i])
                for (int j=i+i;j<=U;j+=i)
                    Vec[j] = true;
        return;
    }
    
    static boolean Proceso(int Num)
    {
        if (Num == 1) return false;
        if (!Vec[Num]) return true;
        Hash = new Hashtable<Integer,Integer>();
        int Count = 0;
        while (Num % 2 == 0) 
        {
            if (Hash.get(2) == null) 
            {
                Hash.put(2,0);
                Count += 2;
            }
            Num /= 2;
        }
        if (Num == 1) return true;
        int Pos = 1; 
        while((Pri[Pos]*Pri[Pos]) <= Num)
        {
            if (Num % Pri[Pos] == 0)
            {
                 if (Hash.get(Pri[Pos]) == null)
                 {
                     Hash.put(Pri[Pos],0);
                     Count += Pri[Pos];
                 }
                 Num /= Pri[Pos];
            }
            else
                Pos++;
        }
        if (Num != 1 && Hash.get(Num) == null)
        {
            Hash.put(Num,0);
            Count += Num;
        }
        return !Vec[Count];
    }    
    static void Load() //Load Only Primes[2,3,5,7,9]
    {
        int Pos = 0;
        for (int i=2;i<=Max;i++) if (!Vec[i]) Pri[Pos++] = i;
        return;
    }
    
    static void Load_Final()//Load True Is The Sum Of Factors Of x is A Prime.....
    {
        for (int i=2;i<=Max;i++)        Final[i] = Proceso(i);
        return;
    }
    public static void main(String[] args) throws Exception
    {
          //BufferedReader In = new BufferedReader(new InputStreamReader (System.in));
          BufferedReader In = new BufferedReader(new FileReader (new File ("In.txt")));
          long xx = System.nanoTime();
          Sieve(2,Max);
          Load();
          Load_Final();
          System.out.println("Cargando "+(System.nanoTime()-xx)/1000000+"ms.");
          StringBuffer MiSol = new StringBuffer();
          while (true)
          {
              StringTokenizer x = new StringTokenizer(In.readLine());
              if (x.countTokens() == 1) break;
              int a = Integer.parseInt(x.nextToken());
              int b = Integer.parseInt(x.nextToken());
              if (a > b)
              {
                  int Aux = a; a = b; b = Aux;
              }
              int Sol = 0;
              for (int i=a;i<=b;i++)                 if (Final[i]) Sol++;
              MiSol.append(Sol).append('\n');
          }
          System.out.print(MiSol);          
          System.out.println((System.nanoTime()-xx)/1000000+"ms.");
    }    
}
[Edited by : Jan] Use code tags.

Re: 11408 - Count DePrimes

Posted: Mon Apr 28, 2008 12:18 pm
by pradeepr
TLE :(

I computed primes using sieves and then used these to evaluate whether an number is Deprime or not and I checked and stored this Deprime condition for every number ,prior to taking input ,but it gives me TLE please help me out!!

attached is my code

Code: Select all

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
        int limit=2236;
        vector<bool> V(limit,true);
        vector<bool> deprimes(5000001,true);
        vector<int> primes;
        V[0]=V[1]=false;
        for(int i=2;i<=limit;i++)
        {
                if(V[i])
                {
                        primes.push_back(i);
                        int reach;
                        for(int j=i;(reach=i*j)<limit;j++)
                        {
                                V[reach]=false;
                        }
                }
        }
        int size=primes.size();
        deprimes[0]=deprimes[1]=false;
        for(int i=3;i<=5000000;i++)
        {
                int temp=i;
                int count=0;
                for(int j=0;j<size && primes[j]*primes[j]<=temp;j++)
                {
                        if(temp%primes[j]==0)
                        {
                                count+=primes[j];
                                while(temp%primes[j]==0)
                                        temp/=primes[j];

                        }

                }
                if(temp!=1)
                        count+=temp;
                for(int j=0;j<size && primes[j]*primes[j] <=count;j++)
                {
                        if((count%primes[j])==0)
                        {
                                deprimes[i]=false;
                                break;
                        }
                }
        }
        int N,M,count;
        while(cin >>N)
        {
                if(N==0)
                        return(0);
                else
                        cin >>M;
                count=0;
                for(int i=N;i<=M;i++)
                {
                        if(deprimes[i])
                                count++;
                }
                cout<<count<<'\n';
        }
        return(0);

}


Re: 11408 - Count DePrimes

Posted: Fri Jun 27, 2008 8:22 am
by nymo
I get ACC with 1.5 s. My basic idea is to have a sieve like approach and then answering query in O(1). There are some very fast solutions to this problem. Any one care to share the idea ? thanks.

Re: 11408 - Count DePrimes

Posted: Fri Jun 27, 2008 5:21 pm
by tanmoy
at last i make it and learn lots of thing :)

Re: 11408 - Count DePrimes

Posted: Sat Jul 05, 2008 8:50 am
by sreejond
i got WA.
But i cant understand why????/
can enyone give me some critical input/output?
Thanks in advance.

sreejond
cuet'06

Re: 11408 - Count DePrimes

Posted: Sat Jul 12, 2008 8:45 pm
by alamgir kabir
I am getting TLE. please help me.
I used sieve method to store all the prime between the range. then find the dePrime and store. I use cumulative array to store
all the sum. but i am getting TLE.
Why??????????
My code is given below

Code: Select all


#include<iostream>
#include<cmath>
#define SIZE 5000003
using namespace std;


bool arr [ SIZE ];
void seive()
{
	long i,j;
	arr[ 1 ] = true;

	for(i = 2; i <= sqrt( SIZE ); i++)
	{
		if( arr[ i ] == false )
		{
			for( j = i; j <= SIZE / i ; j++)
			{
				arr[ i * j ] = true;
			}
		}
	}
	return;
}

long sum_fact [ SIZE ];
long cumul [ SIZE ];
bool fac [ SIZE ];

void factorize()
{
    long num, i, j, sum;
    for(i = 2; i < SIZE; i ++)
    {
        cumul [ i ] = cumul [ i - 1 ];
        if( !arr [ i ] )
        {
            sum_fact [ i ] = i;
            cumul [ i ]++;
            fac [ i ] = true;
            continue;
        }
        num = i;
        for(j = 2, sum = 0; j <= num; j ++)
        {
            if(num % j == 0)
            {
                sum += j;
                num /= j;
                if(num % j == 0) sum += sum_fact [ num ] - j;
                else sum += sum_fact [ num ];
                break;
            }
        }
        if(!arr [ sum ])
        {
            sum_fact [ i ] = sum;
            fac [ i ] = true;
            cumul [ i ] ++;
        }
    }
    return;
}

int main()
{
    seive();
    factorize();
    long a, b;
    while( scanf("%ld%ld", &a, &b) == 2 && a && b )
    {
        if( fac [ a ] || fac [ b ]) printf("%ld",cumul [ b ] - cumul [ a ] + 1);
        else printf("%ld",cumul [ b ] - cumul [ a ]);
        printf("\n");
    }
    return 0;
}



Thanks.

Re: 11408 - Count DePrimes

Posted: Sun Jul 13, 2008 10:09 pm
by sapnil
Take input like this:

Code: Select all

while(scanf("%ld",&a)==1)
{
     if(a==0)
    {
         break;
    }
    scanf("%ld",&b);
}
Thanks

Re: 11408 - Count DePrimes

Posted: Sat Jul 19, 2008 10:55 pm
by alamgir kabir

Code: Select all

cut after ac

Re: 11408 - Count DePrimes

Posted: Fri Sep 19, 2008 8:59 pm
by shakil
Why WA???

Code: Select all

Cut after AC

Re: 11408 - Count DePrimes

Posted: Tue Jun 07, 2011 7:54 am
by iriz7482
I got TLE because my factor funtion is too slow. Are there any fast factorization algorithms for this problem? :roll: :cry:

Code: Select all

long Sum(long n, long a[]) /* a[] stores primes from 2 to 2221 */
{
     long r = 0, i = 0;
     while(n > 1)
     {
          if(isPrime(n,a))
          {
               r += n;
               break;
          }
          while(n%a[i])
          i++;
          while(n%a[i] == 0)
          n /= a[i];
          r += a[i];
     }
     return r;
}