Question

problema in C :
Se da un numar natural. Sa se afiseze cel mai apropiat numar prim față de n.

(programul va contine cel putin un subprogram) , DE explicat metoda de rezolvare !

exemplu: n=24 se va afisa 23, pentru n=26 se va afisa 29.

Answer 1

Am scris 3 functii (subprograme).
Functia prim(n) returneaza daca un numar este prim sau nu. Incepem sa testam potentialii divizori ai unui numar pana la radicalul numarului. Conditia d * d <= n inseamna ca testam pana la radical din n.
Este suficient sa testam potentialii divizori pana la radicalul numarului deoarece divizorii sunt perechi de forma : d1 * d2 = n (ex pentru n = 6 avem urmatoarele perechi :
 1 * 6 = 6
 2 * 3 = 6
Putem sa consideram 1 si 2 ca fac parte din prima grupa (adica d1 ) si 6 si 3 ca fac parte din a doua grupa (adica d2).
Se poate observa ca pentru orice numar, cel mai mare divizor din prima grupa este mai mic sau egal cu radicalul numarului. De aici rezulta ca daca nu avem divizorii in prima grupa (divizori mai mici sau egali cu radical din n) atunci nu exista divizori nici in a doua grupa (divizori mai mari decat radical din n).
Cat timp cele doua conditii se indeplinesc (d * d <= n si n % d != 0), cautam un alt potential divizor. Daca am depasit radicalul numarului  (adica d * d > n ) inseamna ca numarul este prim. Daca nu am depasit radicalul numarului inseamna ca am iesit din while pentru ca a picat a doua conditie (n % d != 0) si am gasit un divizor.

Urmatoarea functie primmaimic(n), ia ca paramentu un numar n si returneaza cel mai mare numar prim, mai mic decat n. Incepem cu un i care initial are valoarea n - 1 si cat timp i nu este prim, incercam un i mai mic.

Functia primmaimare( n) functioneaza similar dar cauta un i mai mare decat n.

In int main() am cautat diferenta cea mai mica dintre :
   n si numarul prim mai mic decat el
si
  numarul prim mai mare decat el si n.


#include <stdio.h>

int prim(int n) {
  int d = 2;
  while(d * d <= n && n % d != 0)
    d++;
  return d * d > n && n > 1;
}
int primmaimic(int n) {
  if(n == 1)
    return 0;
  else {
    int i = n - 1;
    while(!(prim(i)))
      i--;
    return i;
  }
}
int primmaimare(int n) {
  int i = n + 1;
  while(!(prim(i)))
    i++;
  return i;
}
int main(void) {
    int n;
    scanf("%d", &n);
    int maimic = primmaimic( n);
    int maimare = primmaimare( n);
    if( n - maimic < maimare - n)
      printf("%d", maimic);
    else
      printf("%d", maimare);
    return 0;
}