← 返回题目列表

AtCoder · past202306_o

O. 序列和素数

中文机器翻译题面 查看原题

问题陈述

给你整数 N, A,和 B。解决以下问题。

算术序列 S = (S_1, S_2, \dots, S_N) 长度 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.


示例输入 2

99 1 2

示例输出 2

25

有 25 素数不大于 100.


示例输入 3

314159 265358 499999999999

示例输出 3

23166