Sadə ədədlərin cəmi#1352

Sadə ədədlərin cəmi (Həll təhlili)

Sadə ədədlər ardıcıllığını $(2, 3, 5, 7, ...)$ (2, 3, 5, 7, ...) yoxlayırıq və onların cəmini toplayırıq. Cəmi $k$ -ya bölünən kimi, istifadə olunan ədədlərin sayını çıxardırıq.

Misal

İlk beş sadə ədədin cəmi $2 + 3 + 5 + 7 + 11$ 2 + 3 + 5 + 7 + 11 $28$ -ə bərabərdir və $7$ -yə bölünür.

Alqoritmin reallaşdırılması

prime funksiyası $1$ qaytarır, əgər $n$ ədədi sadədirsə.

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++

Proqramın əsas hissəsi. $k$ dəyərini oxuyuruq.

scanf("%d",&k);

$s$ dəyişənində sadə ədədlərin cəmi, $c$ dəyişənində isə onların sayı toplanır.

s = c = 0;

$2$ -dən başlayaraq ədədləri yoxlayırıq. Əgər cari ədəd sadədirsə, onu $s$ -ə əlavə edirik və $c$ -ni artırırıq. Cəmi $s$ $k$ -ya bölünən kimi, döngü dayanır.

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

C++

$k$ -ya bölünən ilk sadə ədədlərin minimal sayını çıxardırıq.

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

Java reallaşdırılması

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 reallaşdırılması

prime funksiyası $1$ qaytarır, əgər $n$ ədədi sadədirsə.

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

Proqramın əsas hissəsi. $k$ dəyərini oxuyuruq.

k = int(input())

$s$ dəyişənində sadə ədədlərin cəmi, $c$ dəyişənində isə onların sayı toplanır.

s = c = 0
i = 2

$2$ -dən başlayaraq ədədləri yoxlayırıq. Əgər cari ədəd sadədirsə, onu $s$ -ə əlavə edirik və $c$ -ni artırırıq. Cəmi $s$ $k$ -ya bölünən kimi, döngü dayanır.

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

$k$ -ya bölünən ilk sadə ədədlərin minimal sayını çıxardırıq.

print(c);