Question

Problema in C sau C++

Se da un numar natural. Sa se afiseze cel mai apropiat numar prim față de n.
(programul va contine cel putin un subprogram)

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

Answer 1

#include <iostream>
using namespace std;
bool isPrim(int);
int main(){
int n=26;
int r=0;
for (int i=1; i<n && r==0; i++){
if (isPrim(n+i)) r=n+i;
else if (isPrim(n-i)) r=n-i;
}
cout << r;
return 0;
}
bool isPrim(int n){
if (n/2*2==n) return false;
if (n/3*3==n) return false;
int i=5; int in=2;
while (i<n){
if (n/i*i==n) return false;
i=i+in;
if (in==2) in=4; else in=2; // 5 7 11 13 17 19 23 25 etc.
}
return true;
}

Answer 2

#include <iostream>
#include <cmath>
using namespace std;

bool prim(int x)
{
   if (x % 2 == 0 && x != 2 || x < 2)
      return false;

   int sq = sqrt(x);
   for (int d = 3; d <= sq; d += 2)
      if (x % d == 0)
          return false;

   return true;
}

int main()
{
   int n, last, x;
   bool k;
  
   cin >> n;

   last = x = 2;
   while (!(k = prim(x)) || x < n)
   {
      if (k)
         last = x;
      x++;
   }

   if (n - last >= x - last)
      cout << last;
   else
      cout << x;
}