Il problema
Ti viene assegnato un n numero. Verifica se il numero n può essere diviso a metà in modo che entrambi i lati di | siano numeri primi.
Esempio:
Input Output
223 2|23
123 Not possible to split.
La mia idea
Mi è stato fornito un esempio di n numero che ha solo tre cifre, e in tal caso sarebbe facile completare l'operazione, ma non è stato stabilito che il n sarà composto da tre cifre, quindi questo rende il problema molto più complesso, secondo me.
Quindi se n potrebbe avere m numero di cifre, farei il successivo. Converti un numero intero in un array e poi implementa una sorta di algoritmo divide et impera. Tuttavia, non sono sicuro di come procederò a confrontare ciascun elemento con il resto degli elementi.
Qualcuno ha qualche idea su come posso completare l'algoritmo? Inoltre, nulla è scolpito nella pietra quindi qualsiasi altro suggerimento sarebbe più che benvenuto.
Aggiornamento
Grazie a tutti ho finito l'algoritmo. Inserirò il mio codice qui sotto.
#include <iostream>
#include <cmath>
using namespace std;
int numberOfDigits(int n)
{
int digits = 0;
if(n < 0)
digits = 1;
while(n)
{
n /= 10;
digits++;
}
return digits;
}
bool isPrime(int n)
{
int isPrime = true;
for(int i = 2; i <= sqrt(n); i++)
{
if(n % i == 0)
{
isPrime = false;
break;
}
}
if(isPrime && n > 1)
return true;
else
return false;
}
int removeLastDigits(int n, int count)
{
return n / pow(10, count);
}
int getLastDigits(int n, int count)
{
return n % (int)pow(10, count);
}
void findPair(int n, int m)
{
int a = n;
int b = m;
int counter = 1;
int digits = numberOfDigits(n);
int arePrimes = 0;
while(digits >= 1)
{
if(isPrime(a) && isPrime(b))
{
cout << a <<"|" << b << endl;
arePrimes = 1;
break;
}
else
{
a = removeLastDigits(n, counter);
b = getLastDigits(n, counter);
counter++;
digits--;
}
}
if(arePrimes == 0)
cout << "Not possible to split." << endl;
}
int main()
{
int n;
cout << "Enter the number: ";
cin >> n;
findPair(n, 0);
}