O - Number Sequence and Prime Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

整数 N,A,B が与えられるので、以下の問題を解いてください。

長さ N の等差数列 S=(S_1,S_2,\dots,S_N) が S_i=A \times (i-1)+B として定義されます。
S にいくつ素数が含まれるか求めてください。

制約

  • 入力は全て整数
  • 1 \le N \le 5 \times 10^5
  • 1 \le A \le 10^6
  • 2 \le B \le 5 \times 10^{11}

入力

入力は以下の形式で標準入力から与えられる。

N A B

出力

答えを整数として出力せよ。

入力例 1

10 3 4

出力例 1

4

S=(4,7,10,13,16,19,22,25,28,31) です。
このうち、素数は 7,13,19,31 の 4 つです。

入力例 2

99 1 2

出力例 2

25

100 以下の素数は全部で 25 個です。

入力例 3

314159 265358 499999999999

出力例 3

23166

Problem Statement

You are given integers N, A, and B. Solve the following problem.

An arithmetic sequence S = (S_1, S_2, \dots, S_N) of length N is defined as S_i = A \times (i - 1) + B.
Find the number of prime numbers in S.

Constraints

  • All input values are integers.
  • 1 \le N \le 5 \times 10^5
  • 1 \le A \le 10^6
  • 2 \le B \le 5 \times 10^{11}

Input

The input is given from Standard Input in the following format:

N A B

Output

Print the answer as an integer.

Sample Input 1

10 3 4

Sample Output 1

4

S = (4, 7, 10, 13, 16, 19, 22, 25, 28, 31).
Among these are four prime numbers: 7, 13, 19, 31.

Sample Input 2

99 1 2

Sample Output 2

25

There are 25 prime numbers not greater than 100.

Sample Input 3

314159 265358 499999999999

Sample Output 3

23166