Primo permissivo (primo) - funziona in locale non online

Aiuto
1

Salve, ho risolto questo problema con questo codice ma non mi da nessun punto, invece sul mio pc risolve benissimo qualsiasi input compresi i casi di esempio…





#include 
#include 
#include 
#include 

char Number[10];
int LengthNumber = 0;
int PositionStars[10];
int NumStars=0;

int GetNumber(int N){
	int i,p=1,R=0;
	for( i = N; i--> 0; ){
		R+= (Number[i]-'0')*p;
		p*=10;
	}
	return R;
}

int IsPrime(int N){
	int divisore = 2;
	while ( divisore <= N/2 ){
		if( N % divisore == 0) return 0;
		else divisore++;
	}
	return 1;
}

int MaxPrimes(int step = 0){
	int Result = 0;
	int pos,k;
	
	pos = PositionStars[step];
	if( step < NumStars ){
		for( k = 0; k <= 9; ++k ){
			Number[pos] = '0' + k;
			Result += MaxPrimes(step+1);
		}
		return Result;
	}
	else
		return IsPrime(GetNumber(LengthNumber));		
	
}

int main(){
	FILE *in, *out;
	in = fopen("input.txt","r");
	out = fopen("output.txt","w");
	
	while ( fscanf(in,"%c",&Number[LengthNumber++]) != EOF) 
		if( Number[LengthNumber-1] == '*' )
			PositionStars[NumStars++] = LengthNumber-1;
	--LengthNumber; //Prende anche EOF
	
	fprintf(out,"%d",MaxPrimes());
	
	fclose(in);fclose(out);
	return 0;	
}
2

Ho provato a fare una piccola correzione nel ciclo di lettura (vicino alla linea 50), prova ad inserire: if((Number[LengthNumber-1]<'0'||Number[LengthNumber-1]>'9')&&Number[LengthNumber-1] != '*') break;

In questo modo termini il ciclo anche se sono presenti caratteri oltre a cifre e asterischi (probabilmente ci sono spazi o a-capo extra nei test). Ho ottenuto senza modificare nient’altro un punteggio di 70/100 (nell’ultimo subtask il programma va in timeout in quasi tutti i test), contro uno di 0/100 senza la correzione.

Buona serata!

3

ah, non ci avevo pensato grazie, ho fatto quella modifica e ora ottengo anch’io 70/100 , per il 100 dovrò trovare un altro algoritmo

4

Prova a pensare se esiste un modo più veloce per controllare se un determinato numero è primo, in particolare prova a pensare se in qualche modo potresti precalcolare già questa informazione :slight_smile: