Problem z kodem

Question

Witam. Mam problem z kodem do zadania do szkoły.

Treść zadania brzmi:

Napisz program, który obliczy ile w podanym przedziale jest liczb, których ostatnia cyfra jest liczbą pierwszą.

A oto mój kod:

#include <iostream>
using namespace std;
int tab[10];
int main()
{
	long long i,n=10,a,b,k,x,s=0,j;
	tab[0]=tab[1]=1;
	for(i=2;i*i<=n;i++)
	if(tab[i]==0)
	{
			
		j=i*i;
		while(j<n)
		{
			tab[j]=1;
			j=j+i;
		}
	}
	cin>>a>>b;
for(k=a;k<=b;k++)
	{
		x=k%10;
		if(tab[x]==0)
		s++;
	}
	cout<<s;
	
}

Niby wszystko jest okej, tylko wrzucając kod do sprawdzenia w jednym punkcie wyrzuca mi przekroczenie limitu czasu. Ma ktoś jakiś pomysł?

Answer 1

Ma ktoś jakiś pomysł?

Po pierwsze: na pewno potrzebujesz z ręki implementować szukanie 1-cyfrowych liczb pierwszych? Są tylko 4, pewnie możesz je z pamięci wymienić ;)

Niby wszystko jest okej, tylko wrzucając kod do sprawdzenia w jednym punkcie wyrzuca mi przekroczenie limitu czasu.

Po drugie: nie trzeba tutaj w ogóle się iterować po tym przedziale. Na przykład spróbuj mi z głowy odpowiedzieć: ile jest w przedziale 10-70 liczb kończących się cyfrą 5? A w przedziale 1000-7000?

Comments

Okej chyba rozumiem, mógłbyś pokazac jak to zapisac w kodzie?

---

Ale co konkretnie? Bo teraz została już prosta matematyka, bez żadnych skomplikowanych rzeczy po stronie C++a; nawet bez pętli.

---

Co 10 liczb występują 4 ktore kończą sie liczbami pierwszymi? O to chodzi?

---

Nie co 10, ale w każdej 10tce.