capajera18 Temat założony przez niniejszego użytkownika |
spoj i liczby pierwsze » 2012-09-08 23:17:54 nie wiem czy ktoś korzysta ze sronki pl.spoj.pl ale ma zadanie takie: Sprawdź, które spośród danych liczb są liczbami pierwszymi Input n - liczba testów n<100000, w kolejnych liniach n liczb z przedziału [1..10000] --Nie rozumiem zabardzo tej liczby testow tu chodzi o to by program wprowadzic w petle ?? --wgl czy moj program jest dobrze napisany czy budzi jakies zastrzeżenia ? Output Dla każdej liczby słowo TAK, jeśli liczba ta jest pierwsza, słowo: NIE, jeśli jest złożona. Example Input: TO DOKŁADNIE MA DZIAŁAĆ JAK W PRZYKLADZIE ? 3 11 1 4 Output: TAK NIE NIE i tj moj kod w jezyku C99: #include <stdio.h>
int main( void )
{
int pierwsza;
int a = 0;
int b = 0;
scanf( "%d", & pierwsza );
if( pierwsza <= 10000 )
{
for( int i = 1; i <= pierwsza; i++ )
{
a = pierwsza % i;
if( a == 0 )
{
b += 1;
}
else;
}
} else;
if( b == 2 )
{
printf( "TAK\n" );
} else printf( "NIE\n" );
return 0;
}
|
|
yoogi |
» 2012-09-08 23:31:18 Niezbyt rozumiem o co ci chodzi :)
http://pl.wikipedia.org/wiki/Algorytm_Euklidesa
Może się przyda :) |
|
capajera18 Temat założony przez niniejszego użytkownika |
» 2012-09-08 23:58:23 ok dzieki ale algorytm euklidesa da sie wykorzystac do liczb pierwszych ?
wiem że podobny problem co ja miał SeaMonster,
właśnie Panie Monster co Pan na to ???
Potrzebna Pana interwencja |
|
diego997 |
» 2012-09-09 00:13:39 Ja bym sprawdzał każdą liczbę z osobna czy nie dzieli się przez 2,3,5 i czy jej pierwiastek nie jest całkowity ;D |
|
capajera18 Temat założony przez niniejszego użytkownika |
» 2012-09-09 00:16:47 diego mógłbyś to tak na przykładzie pokazać , bo o tej porze za wolno myśle i nie rozumiem co napisałeś
bez urazy oczywiście :-)
zalamki mozna dostac, program sie zachowuje w porzadku , ale czy kod dobrze wyraża moje zadanko ? |
|
diego997 |
» 2012-09-09 00:25:02 No bo liczby pierwsze to są tylko te podzielne przez siebie i 1. Czyli np.
2,3,7,123,121(ta nie)
121- podałem celowo ponieważ jeżeli byśmy zrobili tylko warunek 2,3,5 to ta liczba według naszego algorytmu byłaby pierwsza, dobra więć dodamy do wyjątków 11.
Dobra a co z liczbą 289, oczywiście jest pierwsza, ale nie dla naszego algorytmu ;p Więc do wyjątków znowu dodajemy kolejną liczbę tym razem 17, itd. Więc tych wyjątków będzie n. Ale jakby tak spojrzeć na te liczby to widać iż są to wielokrotności liczb pierwszych czyli pierwiastek jest całkowity, zatem zamiast dodawać te n wyjątków wystarczy dodać jeden, który odrzuca pierwiastki całkowite. |
|
capajera18 Temat założony przez niniejszego użytkownika |
» 2012-09-09 00:30:11 ok diego mniej wiecej ciebie rozumiem, a sprawdzałeś jak mój program działa ??
|
|
ison |
» 2012-09-09 00:36:25 | Więc tych wyjątków będzie n. |
Genialne, zasada rozpatrywania n liczb z n wyjątkami :D | zatem zamiast dodawać te n wyjątków wystarczy dodać jeden, który odrzuca pierwiastki całkowite. |
??? Ja bym sprawdzał każdą liczbę z osobna czy nie dzieli się przez 2,3,5 i czy jej pierwiastek nie jest całkowity ;D
|
Sorry, Twój algorytm nie działa :D ok dzieki ale algorytm euklidesa da sie wykorzystac do liczb pierwszych ?
|
nie da --Nie rozumiem zabardzo tej liczby testow tu chodzi o to by program wprowadzic w petle ??
|
po prostu masz ileś liczb do rozpatrzenia, najpierw wczytujesz liczbę testów a potem tyle razy wczytujesz zmienną i sprawdzasz czy jest pierwsza --wgl czy moj program jest dobrze napisany czy budzi jakies zastrzeżenia ?
|
jest za wolny (teraz jest ok, ale jeśli dołożysz liczbę testów to już nie) http://pl.wikipedia.org/wiki/Sito_Eratostenesa |
|
| « 1 » 2 3 4 |