Primo permissivonew

Aiuto
1 
#include <iostream>
#include <string.h>
#include<fstream>
#include <math.h>
#include <algorithm>
using namespace std;
int conteggio=0;
int N;
int is_prime(int n)
{ if (n<2) return 0;
int i;
 int t=(int) sqrt(n);
for(i=2;i<=t; i++)
{
	if (n%i==0) return 0;}
	
	return 1;
	
}

void primi(char s[])
{
	int i, j, nostar =1;
    for (i=0; i<N; i++)
    { if (s[i]=='*') {for (j=0;j<10;j++) {s[i]=j+'0'; primi(s);    }
    
    s[i]='*';
    return ;
    }
    	
    	
    }
if (is_prime(atoi(s))) conteggio++;
}

int main()
{

freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

char s[10];
cin>>s;
N=strlen(s);
primi(s);
cout<<conteggio;


return 0;
}

Chi può dirmi perchè 70/100 ?

2

Senza sapere che errore ottieni mi sembra abbastanza difficile aiutarti. Magari descrivi anche l’algoritmo che usi a parole, può aiutare molto.

1 Mi Piace
3

L’algoritmo ha una complessità troppo alta per risolvere il problema con 100 punti
prova a pensare ad un modo per generare una lista di numeri primi in modo piĂą veloce

4

Anche io ho effettuato 70/100 un bel po di tempo fa, credo che una possibile velocizzazione sia data dalla riduzione dei numeri i da controllare.

Per esempio supponendo che N =100 quindi t=10 invece di controllare il 2 3 4 5 6 7 8 9 e 10 potresti controllare solo $K$numeri che in questo caso sono 4 giusto? , aumentando N aumenterĂ  anche il guadagno di tempo per esempio con N=900, t=30 k=10

5

Ho riprovato a svolgere il problema ma ottenendo ancora 70/100 , l’algoritmo sostanzialmente prende in input la stringa s e la trasforma in un array di char e successivamente un array di int dove l’asterisco viene rappresentato dal -1 per comodità mia, poi genero la lista dei numeri primi che parte dal numero più piccolo e arriva fino al massimo numero che potrebbe corrispondere es.

3*1 ->300<numeri<400
9*** -> 9000<numeri<10000

La mia lista è creata in questo modo>

  • Inserisco inizialmente in una lista contenente tutti i numeri primi il numero 2, ed il numero 3,partendo poi dal numero 5 controllo che non sia un multiplo di nessuno dei numeri primi inseriti precedentemente(mi fermo a sqrt(valore)) se non lo è lo inserisco e svolgo lo stesso calcolo

  • Controllo che il numero inserito possa essere un numero derivato da quello iniziale(senza controllare gli asterischi per il momento ma basandomi soltanto che stia nell’intervallo dei valori possibili), se lo è lo aggiungo all lista dei valori “possibili”

  • Per ogni elemento della lista controllo che per ogni cifra in posizione i il valore corrisponde alla cifra del numero preso in input, tranne nel caso in cui questa cifra sia un * (-1) e li conto

Questo è il codice , devo capire dove velocizzarlo ma credo nella generazione dei numeri primi , lo migliorei usando il Crivello di Eratostene?

EDIT:: Usando il Crivello di Eratostene si ottiene 100/100