33. The favourite numbers of Santa Claus

Santa Claus liked play with numbers and figures. Most of all he liked a number 1 because 1.01 New Year starts.

Years passed, but he stayed be of superstitious – he didn't like numbers, where 3 stand after 1, that is number 13. On New Year he decided to give a new problem: count how many Santa Claus favourite prime numbers contains the interval [a, b]?

Input. Contains two numbers: the start a and the end b of the interval (1 ≤ a ≤ b ≤ 500000).

Output. Print the amount of favourite prime numbers of Santa Claus.

Sample input	Sample output
9 23	4

SOLUTION

Eratosthenes sieve

Algorithm analysis

Run the sieve of Eratosthenes for integers up to 500000. For each query, iterate through all numbers from a to b and calculate how many of them are prime and do not contain 13 in decimal notation.

Example

In the interval [9; 23] there are 4 prime numbers that do not contain 13 in decimal notation. These numbers are 11, 17, 19, 23.

Algorithm realization

Declare a global array to set the primality of numbers.

#define MAX 500100

int primes[MAX];

Function gen_primes fills the array primes to test nimbers for primality.

void gen_primes(void)

{

int i, j;

for(i = 0; i < MAX; i++) primes[i] = 1;

primes[0] = primes[1] = 0;

for(i = 2; i < sqrt(MAX); i++)

if (primes[i])

for(j = i * i; j < MAX; j += i) primes[j] = 0;

}

Function Has13 returns 1, if number n contains 13 in its decimal notation.

int Has13(int n)

{

while(n > 0)

{

if (n % 100 == 13) return 1;

n /= 10;

}

return 0;

}

The main part of the program. Read the input data.

scanf("%d %d",&n,&m);

Run the sieve of Eratosthenes.

gen_primes();

Iterate over numbers from n to m. Count how many of them are prime and do not contain 13 in its decimal notation.

res = 0;

for(i = n; i <= m; i++)

if (primes[i] && !Has13(i)) res++;

Print the answer.

printf("%d\n",res);

Java realization

import java.util.*;

public class Main

{

final static int MAX = 500100;

static boolean[] primes = new boolean[MAX];

public static void gen_primes()

{

int i, j;

Arrays.fill(primes, true);

primes[0] = primes[1] = false;

for(i = 2; i <= Math.sqrt(1.0*MAX); i++)

if (primes[i])

for(j = i * i; j < MAX; j += i) primes[j] = false;

}

public static boolean Has13(int n)

{

while(n > 0)

{

if (n % 100 == 13) return true;

n /= 10;

}

return false;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int a = con.nextInt();

int b = con.nextInt();

gen_primes();

int res = 0;

for(int i = a; i <= b; i++)

if (primes[i] && !Has13(i)) res++;

System.out.println(res);

con.close();

}

}