10533 - Digit Primes

[uvasarker]

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

Code: Select all

/* removed */

[brianfry713]

Try input 3 3, the output should be 1.

[uvasarker]

Thanks a lot boss I got it AC

[@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]

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

[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

[triplemzim]

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

Code: Select all

cout<<"Accepted"<<endl;

[brianfry713]

Input:

Code: Select all

1
13 13

Output should be 0

[triplemzim]

Input:

Code: Select all

1
13 13

Output should be 0

thanks got AC

[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]

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

[brianfry713]

jalil_cse, try running your code on the sample input.

[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]

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

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