10533 - Digit Primes

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by uvasarker » Sun Feb 26, 2012 7:55 pm

Hi boss,
Now, it's WA. Please, help me. Give me some critical test cases. Here is my code:

Code: Select all

/* removed */
Last edited by uvasarker on Mon Feb 27, 2012 8:31 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by brianfry713 » Mon Feb 27, 2012 8:34 am

Try input 3 3, the output should be 1.
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by uvasarker » Mon Feb 27, 2012 2:07 pm

Thanks a lot boss I got it AC

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by @li_kuet » Sun Jul 15, 2012 7:01 pm

Try this Input :

Code: Select all

3
5 5
5 7
1 1000000
Output should be :

Code: Select all

1
2
30123

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by shuvokr » Sun Feb 17, 2013 6:23 pm

Need help.. Got TLE again and again but why ???

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

#define sf scanf
#define pf printf
#define LLU unsigned long long
#define Lu unsigned long
#define LLD long long
#define LD long
int N = 1000000;
bool *status = new bool[1000000], *res = new bool[1000000];
int main()
{
    int sqrtn, i, j;
    for(i = 0; i <= N; i++) status[i] = true;
    for(i = 4; i <= N; i += 2) status[i] = false;
    status[2] = true;

    for(i = 3; i <= 1000; i += 2)
        if(status[i])
            for(j = i * i; j <= N; j += i)
                status[j] = false;

    for(i = 1; i <= N; i++) res[i] = false;

    for(i = 3; i <= N; i += 2)
        if(status[i])
        {
            int sk = i;
            int sum = 0;
            int len = (int)(log10(sk));
            for(int k = 0; k <= len; k++)
            {
                sum += sk % 10;
                sk = sk / 10;
            }
            if(status[sum]) res[i] = true;
        }
    res[2] = true;
    int m, n, T;
    sf("%d", &T);
    while(T--)
    {
        int cou = 0;
        sf("%d%d", &m, &n);
        if(m <= 2) cou = 1;
        if(m % 2 == 0) m = m + 1;
        for(i = m; i <= n; i = i + 2)
            if(res[i]) cou++;
        pf("%d\n", cou);
    }
    return 0;
}

Code: Select all

enjoying life ..... 

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by brianfry713 » Mon Feb 18, 2013 7:05 am

From uhunt:
kannabyz> pre calculate number of digit primes from 1 to 1000000 , when you get t1 & t2 , number of digit primes t2 subtract number of digit primes t1
kannabyz> if t1 = 10, t2 = 100 . Number of digit primes at 10 is 4 and number of digit primes at 100 is 14
kannabyz> 100 - 10 = 14 - 4 = 10
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by triplemzim » Fri Jul 26, 2013 12:05 am

Why getting wrong answer??? Please help... i tried all test cases i found... :(

Code: Select all

cout<<"Accepted"<<endl;
Last edited by triplemzim on Sat Jul 27, 2013 12:31 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by brianfry713 » Sat Jul 27, 2013 3:56 am

Input:

Code: Select all

1
13 13
Output should be 0
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by triplemzim » Sat Jul 27, 2013 12:30 pm

brianfry713 wrote:Input:

Code: Select all

1
13 13
Output should be 0
thanks got AC :)

jalil_cse
New poster
Posts: 8
Joined: Tue Dec 25, 2012 12:35 pm

Post by jalil_cse » Tue Dec 03, 2013 9:43 pm

why wa.......plz help me....

Code: Select all

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
#include<stdlib.h>
#include<math.h>
#include<memory.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<time.h>
using namespace std;
#define pi 2*acos(0.0)
#define inf (1<<30)
#define eps 1e-9
#define mod   1000000007
#define mx7   10000007
#define mx6   1000006
#define mx5   100005
#define ll long long int
#define mx 1000000
bool sie[mx+2];
int prime[mx];
int l=0,c=0;
int temp[mx];
bool add(int n)
{
    int sum=0;
    while(n!=0)
    {
        sum=sum+n%10;
        n=n/10;
    }
    if(sie[sum]==0)
        return true;
    else

        return false;
}
void si()
{
    sie[1]=1;
    prime[l++]=2;
    temp[c++]=1;
    for(int i=4;i<=mx;i=i+2)
        sie[i]=1;
    for(ll i=3;i<=mx;i=i+2)
    {
        if(sie[i]==0)
        {
            prime[l++]=i;
            if(add(i))
                temp[c++]=1+temp[c-1];
            else
                temp[c++]=temp[c-1];
            for(ll j=i*i;j<=mx;j=j+i*2)
                sie[j]=1;
        }
    }
}
int ser(int value,int left,int right)
{
    int mid;
    if(right<left)
        return right;
    mid=floor((left+right)/2);
    if(prime[mid]==value)
        return mid;
    if(prime[mid]>value)
        return ser(value,left,mid-1);
    else
        return ser(value,mid+1,right);
}
int main()
{
   // clock_t a,b;
   // a=clock();
    si();
   // b=clock();
   // cout<<double(b-a) / CLOCKS_PER_SEC  <<endl;
    int t;
    scanf("%d",&t);
    while(t--){
    int n,m;
    scanf("%d %d",&n,&m);
    int low=ser(n,0,l-1);
    if(prime[low]!=n && n>=prime[low+1])
        low++;
        int high=ser(m,0,l-1);
        if(low==0)
            printf("%d\n",temp[high]);
        else
            printf("%d\n",temp[high]-temp[low-1]);
    }
        return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by brianfry713 » Wed Dec 04, 2013 12:00 am

jayanto, you're getting TLE, first run a sieve to find the primes, then store the number of digit primes up to all possible numbers. Your main loop should run in O(1).
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by brianfry713 » Wed Dec 04, 2013 12:01 am

jalil_cse, try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

TLEorWA
New poster
Posts: 12
Joined: Sat Mar 01, 2014 12:56 pm

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by TLEorWA » Sat Mar 01, 2014 1:40 pm

i'm getting TLE again & again.Why??? :(
I'm using bitwise sieve. here is my code -

http://pastebin.com/kHdYJtaq

somebody help me, :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10533 Digit Primes (TLE) why? please help me, please

Post by brianfry713 » Sun Mar 02, 2014 5:27 am

brianfry713 wrote:first run a sieve to find the primes, then store the number of digit primes up to all possible numbers. Your main loop should run in O(1).
Check input and AC output for thousands of problems on uDebug!

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10533 - Digit Primes

Post by bgcsaif » Wed Nov 19, 2014 6:32 am

I am getting TLE for the problem. Can anyone help.me to make it work faster please?

Code: Select all

#include <stdio.h>
#include <math.h>
int prime(int n)
{
	int i, a = 1;
	for (i = 2; i <= sqrt(n); i++)
		if (n % i == 0)
		{
			a = 0;
			break;
		}
	if (n < 2)
		a = 0;
	if (a == 1)
		return 1;
	else
		return 0;
}

int main()
{
	int t, n, m, i, a, sum, c;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d %d", &n, &m);
		c = 0;
		for (i = n; i <= m; i++)
		{
			if (prime(i) == 1)
			{
				a = i, sum = 0;
				while (a != 0)
				{
					sum = sum + (a % 10);
					a = a / 10;
				}
				if (prime(sum) == 1)
					c++;
			}
		}
		printf("%d\n", c);
	}
	return 0;
}

Post Reply

Return to “Volume 105 (10500-10599)”