YoungProgrammer

Back to Problem list

Problem 28: 
An integer substring of an integer is formed by consecutive digits of the original integer.
For example, the number 6158 contains the substrings 6, 1, 5, 8, 61, 15, 58, 615, 158, and 6158.
You must find the largest substring of an integer that is also a prime. 

Input
2319
Output
31


#include<stdio.h>
#include<string.h>

int isPrime(int n) { // this function returns 1 when is prime, otherwise returns 0
    int i;
    if(n == 2) return 1;
    if(n%2 == 0) return 0;
    for(i = 3; i*i<=n; i+=2) {
        if(n%i == 0) return 0;
    }
    return 1;
}

int makeSubstringToNumber(char num[], int low, int up) {
    int i, number = 0, base = 1;
    for(i = up; i>=low; i--) {
        number += (num[i]-'0') * base;
        base *= 10;
    }
    return number;
}

int makeSubstring(char num[], int n) { // This function makes all possible substring of length n
    int i, j, len, max = 0;
    int subnumber;
    len = strlen(num);
    n = n - 1;
    for(i = 0; i<strlen(num); i++) {
        if(i + n >= len) break;
        subnumber = makeSubstringToNumber(num,i,i+n);
        if(isPrime(subnumber)) {
                if(max < subnumber) {
                   max = subnumber;
                }
        }
    }
    return max;
}

void Find(int n) {
    char number[100];
    int found = 0;
    sprintf(number,"%d",n); // converting number to string
    int i, len = strlen(number);
    for(i = len; i>=1; i--) {
        found = makeSubstring(number,i);
        if(found > 0) break; // we find a sub-number which is a prime
        
    }
    if(found) printf("%d\n",found);
    else printf("No Primes\n");
}


int main() {
    int n;
    scanf("%d",&n);
    Find(n);
    return 0;
}

Back to Problem list