12542 - Prime Substring

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

Moderator: Board moderators

Post Reply
alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Location: BUBT,Dhaka, Bangladesh
Contact:

12542 - Prime Substring

Post by alimbubt » Thu Apr 04, 2013 5:40 pm

Input:

Code: Select all

144444444444444442
872368687683485
20983499862347
2347878234
3847567523745
10007893476
999999990007
2378547666666666666666666666237424275475
12345678901234567890
82137482644656
4654451154112115253235221212522322325232035235232323253
2556463416131163143434
51656154531521
45287686
348573856358865
13
197
234786238646238482348
11199999197
38794583656358346563864656386458348583658364563
8080820830477472372720808
82734828452354723950923754729374927
2342342348234823842848923649
9273497274027804207840
0
Output:

Code: Select all

2
87683
62347
7823
67523
10007
90007
7547
78901
2137
35221
6131
16561
7
8573
13
197
78623
99991
94583
83047
84523
8923
74027
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 12542 - Prime Substring

Post by uDebug » Fri Apr 18, 2014 8:52 am

alimbubt,

Thanks for sharing these great test cases.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 12542 - Prime Substring

Post by Repon kumar Roy » Tue May 06, 2014 11:22 pm

I am getting WA ... Here is my code...
I have checked I/O posted here.. It matched everything

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

/*------- Constants---- */
#define MX 1030
#define ll long long
#define ull unsigned long long
#define mod 1000000007

/* -------Global Variables ------ */
ll x,y;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))




int primeGenerator[100099],prime[100000];
char input[300];

template <class T> inline T seive(T n){
    T sqrtN = sqrt(n);
    primeGenerator[0]=primeGenerator[1]=1;
    for (int i=3; i<=sqrtN; i+=2) {
        if(primeGenerator[i]==0){
            for(int j=i*i;j<=n;j+=i+i){
                primeGenerator[j]=1;
            }
        }
    }
    prime[0]=2;
    int j=1;
    for(int i=3;i<=500;i+=2){
        if(primeGenerator[i]==0) {
            prime[j++]=i;
        }
    }
    return j;
}


int primeTest(int sum)
{
    if(sum<2) return 0;
    for(int i=0;prime[i]<=sqrt(sum);i++){
        if(sum%prime[i]==0) return 0;
    }
    return 1;
}
int main()

{
    int i,j,len=(int)strlen(input),sum,answer,max;
    seive(100099);
    while (scanf("%s",input)) {
        if(input[0]=='0') return 0;
        max=-1;
        answer=-1;
        len=(int)strlen(input);
        for (i=0; i<len; i++) {
            sum=0;
            for (j=i;input[j]; j++) {
                sum=sum*10+ input[j]-'0';
                if(sum>100000) break;
                if(sum>answer && primeTest(sum)) {
                    answer=sum;
                }
                
            }
        }
        printf("%d\n",answer);
    }
    return 0;
}

Again If there is no prime in the string like 44 , 9 as an input

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 12542 - Prime Substring

Post by uDebug » Wed May 07, 2014 7:54 am

Repon kumar Roy wrote:I am getting WA ...
How does your code compile? You use the function strlen() but don't have the line

Code: Select all

#include<cstring>
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

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

Re: 12542 - Prime Substring

Post by brianfry713 » Wed May 07, 2014 9:28 pm

Fix the compile errors, and try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 125 (12500-12599)”