All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
marco2509
New poster
Posts: 3 Joined: Wed Oct 28, 2009 10:59 pm
Post
by marco2509 » Wed Oct 28, 2009 11:08 pm
I need help with my code, I don't know where is the mistake, I received "Factorial Factors has failed with verdict Time limit exceeded". I think is the input.
Code: Select all
#include <stdio.h>
#include <stdlib.h>
using namespace std;
long int *array;
void primos(long int numero)
{
int factor = 2;
while(numero >= factor*factor) {
if(!(numero % factor)) {
array[factor]++;
numero = numero / factor;
continue;
}
if(factor == 2) factor++;
else factor += 2;
}
array[numero]++;
}
int principal()
{
long int numero;
int factor;
long int res=0;
char line[10];
printf("Introduce un numero entero: ");
gets(line);
numero= (long int) atoi(line);
if(numero==0)
return 1;
array=new long int[numero];
for(long int i = 0; i <= numero; ++i) array[i] = 0;
for(long int i = 2; i <= numero; ++i)
primos(i);
for(long int i = 2; i <= numero; ++i)
if(array[i]!=0)
res=res+array[i];
printf("%ld\n",res);
return 0;
}
int main() {
while (principal()==0)
delete array;
return 0;
}
seraph
New poster
Posts: 9 Joined: Tue Dec 15, 2009 4:18 pm
Post
by seraph » Wed Jan 13, 2010 5:42 pm
where is my mistake in this program?
i always got TLE
Code: Select all
#include <iostream>
#include <vector>
using namespace std;
int arr[1000001]={0};
vector<int> v;
int main()
{
bool prime[1000001]={0};
prime[0]=1;
prime[1]=1;
for (int i=2;i<=1000000;i++)
{
if (prime[i]==0)
{
v.push_back(i);
int temp=i+i;
while (temp<=1000000)
{
prime[temp]=1;
temp+=i;
}
}
}
int count=0;
int n;
while (cin>>n)
{
count=0;
int total=0;
for (int i=2;i<=n;i++)
{
if (arr[i]!=0)
{
total+=arr[i];
continue;
}
if (prime[i]==0)
{
arr[i]=1;
//cout<<" 1 ";
total++;
continue;
}
count=0;
int temp=i,j=0;
while (temp!=1)
{
if (arr[temp]>0)
{
count+=arr[temp];
break;
}
if (temp%v[j]==0)
{
temp/=v[j];
count++;
}
else
j++;
}
//cout<<"count : "<<count;
total+=count;
arr[i]=count;
}
cout<<total<<endl;
}
return 0;
}
fkrafi
New poster
Posts: 13 Joined: Wed Sep 15, 2010 1:36 pm
Post
by fkrafi » Wed Oct 06, 2010 7:54 pm
Code: Select all
#include<stdio.h>
#include<math.h>
int prime[1000010], prm[1000010], sz;
void sieve(int n)
{
prime[0]=1;
prime[1]=1;
int m = int(sqrt(n)), i=2, k;
for(k=i*i; k<=n; k+=i)
prime[k]=1;
for (i=3; i<=m; i+=2)
if(!prime[i])
for (k=i*i; k<=n; k+=i)
prime[k]=1;
}
void only_primes()
{
prm[0] = 2;
sz = 1;
for(int i=3; i<=1000010; i+=2)
if(!prime[i])
prm[sz++] = i;
}
long int no_prime(long int n)
{
int i, t;
long int cnt=0;
for(i=0; (i<sz && prm[i]<=n); i++)
{
t = n;
while(t/prm[i])
{
cnt += (t/prm[i]);
t /= prm[i];
}
}
return cnt;
}
int main()
{
int n;
long int res;
sieve(1000010);
only_primes();
while(scanf("%d", &n) != EOF)
{
res = no_prime(n);
printf("%ld\n", res);
}
return 0;
}
@mjad
New poster
Posts: 44 Joined: Thu Jul 22, 2010 9:42 am
Post
by @mjad » Tue Oct 19, 2010 2:27 pm
Here is my code I think this is so efficient
Code: Select all
#include<stdio.h>
#define M 1000002
int *prime =new int[M];
long *pre =new long[M];
int isprime()
{
long i,j;
for(i=0;i<M;i++)
{
pre[i]=prime[i]=0;
}
for(i=2;i*i<=M-2;i++)
if(!prime[i])
for(j=i+i;j<=M-2;j+=i)
prime[j]=1;
return 0;
}
long divsor(long n)
{
long d,total=0,i,j;
j=n;
for(i=2;i*i<=n;i++)
{
if(!prime[i])
{
d=0;
if(pre[n/i]!=0&&n%i==0)
{
pre[j]=pre[n/i]+1;
return pre[j];
}
while(n%i==0)
{
d++;
n/=i;
}
total+=d;
}
}
if(n!=1)
total++;
pre[j]=total;
}
int main()
{
long a,b,r;
int t;
t=isprime();
//freopen("884.txt","r",stdin);
while(scanf("%ld",&a)==1)
{
r=0;
for(b=2;b<=a;b++)
r+=divsor(b);
printf("%ld\n",r);
}
return 0;
}
sazzadcsedu
Experienced poster
Posts: 136 Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:
Post
by sazzadcsedu » Tue Oct 19, 2010 10:03 pm
No, I don't think so.Here is an efficient way-
I have no time to explain my code.So its upto you to understand the code.Dont submit it without understanding.And let me know after copying so that i can remove it.
Last edited by
sazzadcsedu on Tue Oct 19, 2010 10:45 pm, edited 2 times in total.
@mjad
New poster
Posts: 44 Joined: Thu Jul 22, 2010 9:42 am
Post
by @mjad » Tue Oct 19, 2010 10:12 pm
Thanks for your reply
i am trying to understand.
you may remove it now.
@mjad
New poster
Posts: 44 Joined: Thu Jul 22, 2010 9:42 am
Post
by @mjad » Wed Oct 20, 2010 4:55 am
i don't understand properly ?
so concept not clear .
Please discuss your Code
thanks for your help
Bamzi
New poster
Posts: 1 Joined: Tue Aug 30, 2011 10:15 am
Post
by Bamzi » Tue Aug 30, 2011 10:16 am
what do you mean when you say to modify the sieve code? In which way? What do you want to get
hotel Thailand Directory with this modification?
Last edited by
Bamzi on Wed May 29, 2013 2:15 pm, edited 1 time in total.
Scarecrow
Learning poster
Posts: 69 Joined: Wed Oct 19, 2011 9:06 pm
Post
by Scarecrow » Fri Jun 01, 2012 12:16 am
getting TLE. can't make the code faster. can someone help me plz
Last edited by
Scarecrow on Sun Jun 03, 2012 10:02 pm, edited 1 time in total.
Do or do not. There is no try.
brianfry713
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Fri Jun 01, 2012 11:53 pm
Precompute the answers for all n. Can you see a relationship between the results for n and n-1?
Check input and AC output for thousands of problems on
uDebug !
Scarecrow
Learning poster
Posts: 69 Joined: Wed Oct 19, 2011 9:06 pm
Post
by Scarecrow » Sun Jun 03, 2012 10:01 pm
thanks
i used a simple DP and your hint of the relation between the results of n and n-1 was very much helpful
Do or do not. There is no try.
mobarak.islam
New poster
Posts: 38 Joined: Wed Dec 05, 2012 11:29 pm
Post
by mobarak.islam » Tue Jun 11, 2013 2:26 pm
I'm getting TLE here. Someone please help me.
Code deleted after AC.
Last edited by
mobarak.islam on Tue Jun 11, 2013 3:17 pm, edited 1 time in total.
t.tahasin
New poster
Posts: 38 Joined: Tue May 28, 2013 11:21 pm
Post
by t.tahasin » Tue Jun 11, 2013 2:35 pm
Hi Mobarak, I checked your code. Change the code portion as following
Code: Select all
while( prime[ind]*prime[ind]<=x)
{
if(x%prime[ind] == 0)
{
x=x/prime[ind];
count++;
ind = -1;
}
ind++;
}
if(x>1) count++;
You don't need to check
prime[ind]<=x rather check
square(prime[ind])<=x . This will reduce your complexity from N to sqrt(N). cause if
prime[ind] is greater than
sqrt(x) then x must not be divisible by any other prime rather than x itself(In that case x is a prime, so increment the count by 1).
Hope you understood.
mobarak.islam
New poster
Posts: 38 Joined: Wed Dec 05, 2012 11:29 pm
Post
by mobarak.islam » Tue Jun 11, 2013 3:16 pm
@t.tahasin :Thanks for your great help. I got AC
mahade hasan
Learning poster
Posts: 87 Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh
Post
by mahade hasan » Thu Oct 31, 2013 10:01 pm
getting tle
need help
any idea to get me out of tle
Code: Select all
#include<stdio.h>
#include<math.h>
bool Status[1000002]={0};
long Data[1003]={0,2},Ary[1000002];
void Cal()
{
long N=7928,I,K;
for(I=3;I<1001;I+=2){
if(!Status[I]){
for(K=I*I;K<=N;K+=I+I)
Status[K]=1;
}
}
K=1;
for(I=3;I<=N;I+=2)
if(!Status[I]){
Data[++K]=I;
if(K>1000) break;
}
//printf("%ld %ld\n",I,K);
}
int main()
{
long I,K,L,M,N,A;
Cal();
for(A=2;A<1000001;A++){
L=sqrt(A);
K=0;
N=A;
for(I=1;I<=L&&N>1;I++){
//if(N%2!=0&&!Status[N]) {K++;break;}
if(A>N) {K+=Ary[N];break;}
else{
M=0;
while(N%Data[I]==0){
++M;
N/=Data[I];
if(A>N) {K+=Ary[N];N=0;break;}
}
K+=M;
}
}
Ary[A]=K;
if(A%2!=0&&K==0) Ary[A]++;
}
while(scanf("%ld",&N)==1){
K=0;
for(A=2;A<=N;A++) K+=Ary[A];
printf("%ld\n",K);
}
return 0;
}
[/color]
we r surrounded by happiness
need eyes to feel it!