Сума простих чисел#1352

Сума простих чисел (Розбір)

Перебираем последовательність простих чисел $(2, 3, 5, 7, ...)$ (2, 3, 5, 7, ...) і накопичуємо їх суму. Як тільки ця сума буде ділитися на число $k$ без залишку, виводимо кількість використаних доданків.

Приклад

Сума перших п'яти простих чисел $2 + 3 + 5 + 7 + 11$ 2 + 3 + 5 + 7 + 11 дорівнює $28$ і ділиться на $7$ .

Реалізація алгоритму

Функція prime повертає $1$ , якщо число $n$ є простим.

int prime(int n)
{
  if (n == 2) return 1;
  if (n % 2 == 0) return 0;
  for(int i = 3; i <= sqrt(n); i += 2)
    if(n % i == 0) return 0;
  return 1;
}

C++

Основна частина програми. Читаємо значення $k$ .

scanf("%d",&k);

У змінній $s$ накопичується сума простих чисел, а в змінній $c$ — їх кількість.

s = c = 0;

Перебираємо числа, починаючи з $2$ . Якщо поточне число просте, додаємо його до $s$ і збільшуємо $c$ . Як тільки сума $s$ стає кратною $k$ , виконання циклу зупиняється.

for(i = 2;; i++)
{
  if (prime(i))
  {
    s += i; c++;
    if (s % k == 0) break;
  }
}

C++

Виводимо мінімальну кількість перших простих чисел, сума яких ділиться на $k$ .

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

Java реалізація

import java.util.*;

public class Main
{
  public static boolean prime(int n)
  {
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for(int i = 3; i <= Math.sqrt(n); i += 2)
      if(n % i == 0) return false;
    return true;
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int k = con.nextInt();
    int s = 0, c = 0;
    for(int i = 2;; i++)
    {
      if (prime(i))
      {
        s += i; c++;
        if (s % k == 0) break;
      }
    }
    System.out.println(c);
    con.close();
  }
}

Java

Python реалізація

Функція prime повертає $1$ , якщо число $n$ є простим.

def prime(n):
  if n == 2: return True
  if n % 2 == 0: return False
  for i in range(3, int(math.sqrt(n))+1, 2):
    if n % i == 0: return False
  return True

Основна частина програми. Читаємо значення $k$ .

k = int(input())

У змінній $s$ накопичується сума простих чисел, а в змінній $c$ — їх кількість.

s = c = 0
i = 2

while True:
  if (prime(i)):
    s += i
    c += 1
    if s % k == 0: break
  i += 1

Виводимо мінімальну кількість перших простих чисел, сума яких ділиться на k.

print(c);