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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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