Znalezienie liczb o podanych kryteriach

0

Algorytm mam chyba dobry, bo w 1 i 2 podpunkcie miałem szukać takich "specjalnych" liczb z przedziału od 1 do 20, no i od 21 do 1000.
A w c) mam już szukać od 1001 do 1000000.. Myślałem, że to na początku zmienna, ale przecież może ona tyle pomieścić... Więc o co chodzi?
Program działa tak, jakby się nie kończył. Co trzeba poprawić? Nie mogę doszukać się błędu.

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

bool dzielniki(unsigned int n)
{
	for(unsigned int i=2; i<n; i++)
 		{
 		if(n%i==0)
 			{
 				if(i%3==1) return false;
 			}
 		}

return true;
}


int main(int argc, char** argv) 
{
	unsigned int n=0;
	unsigned int i=0;
	int a=0;
	int b=0;
	unsigned int c=0;
	int d=0;
	
	ofstream plik("zadanie4.txt");

//a
	for(n=2; n<=20; n++)
		{
		if(n%3==1)
			{
			
			if(dzielniki(n))
				a++;
			
			}
		}
//b	
	for(n=21; n<=1000; n++)
		{
		if(n%3==1)
			{
			
			if(dzielniki(n))
				b++;
			
			}
		}
//c	
	for(n=1001; n<=1000000; n++)
		{
		if(n%3==1)
			{
			
			if(dzielniki(n))
				c++;
			
			}
		}


	plik << "a) " << a << endl;
	plik << "b) " << b << endl;
	cout << c;
	return 0;
}
1

Złożoność twojego algorytmu to O(n^2), a w c) masz do sprawdzenia ~1000000 liczb, więc "trochę" to potrwa.

Podaj treść zadania.

0

ostatnią zmienną c wyrzucasz na ekranie cout zamiast zapisać do pliku ;) Jak chcesz zobaczyć na ekranie to daj getch(); żeby zatrzymać program przed zamknięciem konsoli.

0

Zapisywałem do pliku, ale chciałem podglądać co się dzieje, dlatego dawałem na ekran :)
Tutaj jest zadanie --> http://kraczkowski.info/wp-content/uploads/2011/09/informatyka_PR_II.pdf

2

Nic dziwnego bo próbujesz wykonać jakieś 2E12 dzieleń - na oko jakieś 3 godziny.
Poniżej masz zoptymalizowany twój program:

#include <iostream>
using namespace std;
 
bool dzielniki(unsigned int n)
  {
   for(unsigned i=4; i<n; i+=3) if(!(n%i)) return false;
   return true;
  }

int main()
  {
   unsigned n,a=0,b=0,c=0;
   ofstream fout("zadanie4.txt");
   for(n=4;n<=20;n+=3) if(dzielniki(n)) ++a;
   fout << "a) "<<a<<endl;
   for(n=22;n<=1000;n+=3) if(dzielniki(n)) ++b;
   fout << "b) "<<b<<endl;
   for(n=1003;n<=1000000;n+=3) if(dzielniki(n)) ++c;
   fout << "c) "<<c<<endl;
   return 0;
  }

ale to i tak zdecydowanie za mało, poczytaj o Sito Eratostenesa.

0

A dlaczego program daje zły wynik dla c) skoro dla b i c jest dobrze. Przecież w C niczym się nie różni, tylko złożonością czasową tak jak mówicie, i tym, że ma sprawdzić więcej liczb..

1 użytkowników online, w tym zalogowanych: 0, gości: 1