AT_past202306_o 数列と素数

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

The input is given from Standard Input in the following format: > $ N $ $ A $ $ B $

Print the answer as an integer.

### Sample Explanation 1 $ S = (4, 7, 10, 13, 16, 19, 22, 25, 28, 31) $ . Among these are four prime numbers: $ 7, 13, 19, 31 $ . ### Sample Explanation 2 There are $ 25 $ prime numbers not greater than $ 100 $ . ### 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} $