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

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm

11408 - Count DePrimes

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;
int prime;

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

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

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

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...       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;
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];
}
{
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
{
long xx = System.nanoTime();
Sieve(2,Max);
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.

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

Re: 11408 - Count DePrimes

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=V=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=deprimes=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

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

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.

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

Re: 11408 - Count DePrimes

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

sreejond
cuet'06

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

Re: 11408 - Count DePrimes

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

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

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

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

I got TLE because my factor funtion is too slow. Are there any fast factorization algorithms for this problem?  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;
}