11408 - Count DePrimes

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

Post Reply
turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

11408 - Count DePrimes

Post by turcse143 » Mon Mar 31, 2008 9:26 pm

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;
	}
}
''I want to be most laziest person in the world''

fidels
New poster
Posts: 6
Joined: Thu Jan 25, 2007 4:07 pm
Location: La Plata, Argentina

Re: 11408,deprimes i got TLE WHATS my problem

Post by fidels » Tue Apr 01, 2008 10:41 pm

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!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: 11408 - Count DePrimes

Post by sclo » Wed Apr 02, 2008 4:17 am

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.

ChiperOrtizII
New poster
Posts: 2
Joined: Mon Apr 14, 2008 7:44 pm

Count DePrimes TL

Post by ChiperOrtizII » Fri Apr 18, 2008 7:19 am

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.

pradeepr
New poster
Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

Re: 11408 - Count DePrimes

Post by pradeepr » Mon Apr 28, 2008 12:18 pm

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

}


nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 11408 - Count DePrimes

Post by nymo » Fri Jun 27, 2008 8:22 am

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.
regards,
nymo

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 11408 - Count DePrimes

Post by tanmoy » Fri Jun 27, 2008 5:21 pm

at last i make it and learn lots of thing :)
Last edited by tanmoy on Tue Sep 23, 2008 8:39 am, edited 2 times in total.

User avatar
sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

Re: 11408 - Count DePrimes

Post by sreejond » Sat Jul 05, 2008 8:50 am

i got WA.
But i cant understand why????/
can enyone give me some critical input/output?
Thanks in advance.

sreejond
cuet'06

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

Re: 11408 - Count DePrimes

Post by alamgir kabir » Sat Jul 12, 2008 8:45 pm

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.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 11408 - Count DePrimes

Post by sapnil » Sun Jul 13, 2008 10:09 pm

Take input like this:

Code: Select all

while(scanf("%ld",&a)==1)
{
     if(a==0)
    {
         break;
    }
    scanf("%ld",&b);
}
Thanks
"Dream Is The Key To Success"

@@@ Jony @@@

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

Re: 11408 - Count DePrimes

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

Code: Select all

cut after ac
Last edited by alamgir kabir on Thu May 14, 2009 5:04 pm, edited 1 time in total.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Re: 11408 - Count DePrimes

Post by shakil » Fri Sep 19, 2008 8:59 pm

Why WA???

Code: Select all

Cut after AC
SHAKIL

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

Re: 11408 - Count DePrimes

Post by iriz7482 » Tue Jun 07, 2011 7:54 am

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

Post Reply

Return to “Volume 114 (11400-11499)”