Sito Eratostenesa

ERATOSTENES

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

main()
{
int i,j,n,a[1000];

printf("ERATOSTENES");

for(i=0;i<=1000;i++)
{a[i]=0;}

for(i=2;j<=sqrt(i);j++)
{if(i%j==0)
break;
if(j>=sqrt(i))
printf("%d",i); 
}

for(i=2;i<1000;i++)
{if(a[i]==1)
{ j=i;
do
{ j=j+i;
a[i]=0; }
while (j==1000);}

for(i=2;i<=1000;i++){
if(a[i]=1) printf("%d ",i);
}

getchar();
getchar();}

}

Co tu jest nie tak ? :c
Może ktoś napisac ? :)

Tabulatorów brakuje ;>

	int dzielnik = 2;
	vector <int> sito(1, 2); // Pierwszy domyślny element w sicie - liczba 2
	
	// Wypelniamy zbior liczbami od 3 do liczba
	for (int x = 3; x <= liczba; x++)
		sito.push_back(x);
	
	// Usuwanie liczb nie-pierwszych | Pierw dzielniki liczby 2, potem liczby 3, (czworka po drodze odpadla), 5..
	do
	{	
		for (int x = 2; x < sito.size(); x++)
			if (sito[x] % dzielnik == 0)
				sito.erase(sito.begin()+x);
				
		dzielnik = sito[numer++];
	}
	while (dzielnik != sito.back());

Wynikiem vectora sito są liczby pierwsze od 2 do liczba

Tylko, że na lekcji nie braliśmy jeszcze takich nowych push itp. więc wie ktoś może jak to poprawić ? co zrobić ?

Nie lepiej zrobić to na tablicy bool? Przykładowy kod zliczający liczbę liczb pierwszych występujących przed podaną, można łatwo przerobić na wypisywanie:

#include <stdio.h>
#include <math.h>
#include <string.h>
#define usi unsigned short int
int main() {
	usi liczba, granica;
	scanf("%hu", &liczba);
	granica=sqrt(liczba);
	bool liczby[liczba];
	memset(liczby, 1, liczba*sizeof(usi));
	liczby[0]=false;
	liczby[1]=false;
	for (usi i=2; i<=granica; i++)
	{
		if (i==false) continue;
		for (usi j=2; j*i<liczba; j++)
			liczby[i*j]=false;
	}
	usi counter=0;
	for(usi i=0; i<liczba; i++)
		if (liczby[i]==true) counter++;
	printf("%hu", counter);
} 

No jakbyśmy to brali na lekcjach to bym na pewno mógł zrobić na tablicach "bool", więc ja czekam na zwykły kodzik, normalnymi pętlami, normalnymi tablicami :)

piotrek94 napisał(a)

No jakbyśmy to brali na lekcjach to bym na pewno mógł zrobić na tablicach "bool", więc ja czekam na zwykły kodzik, normalnymi pętlami, normalnymi tablicami :)

A ja czekam na gorącą kawę ze śmietanką.

Visher: sito z procentami
merlinnot: for (usi j=2; j*i<liczba, jakie 2?
Piotrze, twoje też do chrzanu, poczytaj wiki

A może chciałbyś się czegoś nauczyć :) Tablica bool przechowuje wartości 0 albo 1. 1 oznacza prawdę, zero oznacza nieprawdę. To tak w skrócie. Oprócz tego może ci się przydać coś z tego:

#include <stdio.h>
#include <string.h>
// potrzebne do funkcji memset, bardzo przydatnej
#define ui unsigned int
// zdefiniowanie "ui" jako "unsigned int"
int main()
{
        ui lenght; 
        scanf("%u ", &lenght); // spacja "pochłania" białe znaki
        ui tab[200]; // tablica unsigned int (liczb naturalnych (z zerem))
        memset(tab, 0, 200*sizeof(ui)); // wypełnienie zerami bloku pamięci o początku w tab, rozmiarze 200*ilość pamięci zajmowana przez unsigned int 

PS. Gorąca kawa to świetny pomysł!

merlinnot napisał(a)

A może chciałbyś się czegoś nauczyć[...]
przykład dość marny

Przed chwilą wpadłem na taki pomysł. przede wszystkim, nie ma sensu iterować każdej liczby pokolei, iterujemy co drugą poczynając od 3.
Jeżeli znamy pierwsze 2 pierwsze liczby pierwsze, to sprawdzamy liczbę czy jest pierwszą dla liczb mniejszych od pierwiastka liczby sprawdzanej. Np:
Jeżeli mamy pierwsze[] = {2, 3}
to sprawdzamy 5 % 3 != 0 - czyli 5 jest liczbą pierwszą
sprawdzamy 7 % 3 != 0 - czyli 7 jest liczbą pierwszą
sprawdzamy 9 % 3 == 0 - czyli 9 nie jest liczbą pierwszą
sprawdzamy 11 % 3 != 0- czyli jest liczbą pierwszą
...
sprawdzamy 19 % 3 != 0 - czyli jest l. pierwszą
...
sprawdzamy 25 % 3 != 0, sprawdzamy 25 % 5 == 0 - czyli nie jest liczbą pierwszą
sprawdzamy 27 % 3 == 0 - przerywamy
sprawdzamy 29 % 3 != 0 , sprawdzamy 29 % 5 != 0 - czyli jest liczbą pierwszą, itd.

Sprawdzamy podzielność tylko przez liczby pierwsze które trzymamy w tablicy, a oto kod:

#include <iostream>
using namespace std;

int main()
{
	const int MAX = 100;
	int zakres = 1, nxt = 2;
	bool pierwsza = true;
	int pierwsze[MAX] = {2, 3};

	for(int i = 3; i < MAX; i += 2)
	{
		if(sqrt(double(i)) == pierwsze[zakres + 1])
			++zakres;

		for(int j = 1; j <= zakres; ++j)
		{
			if(!(i % pierwsze[j]))
			{
				pierwsza = false;
				break;
			}
			else
				pierwsza = true;
		}

		if(pierwsza)
			pierwsze[nxt++] = i;
	}

	for(int i = 0; i < nxt; ++i)
		cout << pierwsze[i] << endl;

	getchar();
	return 0;
}

po pierwsze primo
fajnie, że na to wpadłeś, bardzo fajny sposób bo próbujesz dzielić tylko przez pierwsze które znalazłeś wcześniej, brawo
(ale wiesz, wymyśliłeś właśnie koło :-) )
po drugie, ważniejsze primo, to nie jest sito Eratostenesa.