Gdybyś zaimplementował Rabina-Millera to by pewnie działało...
Niestety po zaimplementowaniu Millera-Rabina i tak mi wywala błędną odpowiedź.
#include <stdio.h>
#include <stdlib.h>
#include <ctime>
int powerOf2[31] =
{ 1<<0, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6,
1<<7, 1<<8, 1<<9, 1<<10, 1<<11, 1<<12, 1<<13,
1<<14, 1<<15, 1<<16, 1<<17, 1<<18, 1<<19, 1<<20,
1<<21, 1<<22, 1<<23, 1<<24, 1<<25, 1<<26, 1<<27,
1<<28, 1<<29, 1<<30 };
// calculates a^b mod m
int power_modulo_fast(int a, int b, int m)
{
int i;
int result = 1;
long int x = a%m;
for (i=1; i<=b; i<<=1)
{
x %= m;
if ((b&i) != 0)
{
result *= x;
result %= m;
}
x *= x;
}
return result;
}
//Miller-Rabin test
int Miller_Rabin(int n, int k)
{
int s = 0;
int s2 = 1;
int a, d, i, r, prime;
srand(time(NULL));
if (n<4)
{
return 1;
}
if (n%2 == 0)
{
return 0;
}
// calculate s and d
while ((s2 & (n-1)) == 0)
{
s += 1;
s2 <<= 1;
}
d = n/s2;
// try k times
for (i=0; i<k; i++)
{
a = 1+(int) ((n-1)*rand()/(RAND_MAX+1.0));
if (power_modulo_fast(a, d, n) != 1)
{
prime = 0;
for (r=0; r<=s-1; r++)
{
if (power_modulo_fast(a, powerOf2[r]*d, n) == n - 1)
{
prime = 1;
break;
}
}
if (prime == 0)
{
return 0;
}
}
}
return 1;
}
int main()
{
int k=30;
int c;
int f=0;
scanf("%d", &c);
int n[c];
while (scanf("%d", &n[f])!=EOF) f++;
for (int i=0; i<c; i++)
{
if (Miller_Rabin(n[i], k) == 1)
{
printf("TAK\n");
}
else
{
printf("NIE\n");
}
}
return 0;
}1 year later
Fabs jest do double'a, a Ty masz inty.
Przeczytaj "regulamin" - tam masz wskazówki, jak postępować ze zmiennymi zmiennoprzecinkowymi.
Poza tym wywal goto, bo jest ryzykowny.
No i radzę po prostu poczytać o algorytmach sprawdzania, czy liczba jest pierwsza:
-brut ( O(t*sqrt n) )
-sito Eratostenesa
-sito Atkina-Bernsteina (trudniejsze)
-chiński test pierwszości
-test Millera-Rabina
Prędzej czy później będziesz się musiał tego nauczyć, więc czemu nie zacząć od teraz? (polecam pierwsze 2 - są najłatwiejsze)
3 years later
Powinieneś starać się samodzielnie rozwiązywać problemy. Jeżeli jednak nie udaje Ci się, to tutaj poszukaj odpowiedzi na swoje pytanie do zadania: Liczby Pierwsze309. Jeżeli tu jej nie znajdziesz, jest to najlepsze miejsce aby zadać pytanie.
[color=#008000]=====================================================================================================================[/color]
Q: Czy to zadanie jest najłątwiejszym zadaniem?
A: Nie. Zadania nie są uporządkowanenie ze względu na trudność, lecz chronologicznie, wg daty powstania. Łatwiejszm zadaniem, jest zadanie próbne40. Możesz także odwiedzić: Podstawy Programowania54
[color=#008000]=====================================================================================================================[/color]
Q: Dlaczego input to cztery liczby, a output to tylko 3 odpowiedzi?
A: Może stanie się to bardziej jasne, gdy zapiszemy input i output w poniższy sposób:
Input:[tab][/tab]Output:
3
[color=#FF0000][b]11[tab][/tab][tab][/tab]TAK
1[tab][/tab][tab][/tab]NIE
4[tab][/tab][tab][/tab]NIE[/b][/color]
[color=#008000]=====================================================================================================================[/color]
[color=#008000]Komentarze pod zadaniem:[/color]
2015-02-16 11:49:46 [color=#0000BF]narbej[/color]
Pytania i odpowiedzi do zadania: Q/A
2014-11-15 15:04:21 [color=#0000BF]Marcin Majak[/color]
-.-
"NIE", a nie "nie"
"TAK", a nie "tak"
i działa...
2011-06-27 18:14:35 [color=#0000BF]Krzysztof Lewko[/color]
Wersja troszkę hard 
spoj.pl/problems/PON/31
[color=#008000]=====================================================================================================================[/color]
Q: Czy 1 i 2 to liczby pierwsze?
A: Liczba [color=#000080]2[/color] TAK, liczba [color=#000080]1[/color] NIE
[color=#008000]=====================================================================================================================[/color]
Q: Czy tu na forum obowiązują jakieś zasady?
A: Oczywiście, że nie. Tu całkowicie panuje wolna amerykanka. Ale czym bardziej się postarasz, tym masz większą szansę na otrzymanie bardziej sensownej odpowiedzi. W przeciwnym wypadku narazisz się na "gniew" moderatora i twój post może ulec "zniszczeniu". Dlatego warto, przed wysłaniem postu, a nawet, jeszcze przed napisaniem, poczytać: Przeczytaj, zanim napiszesz ...5
[color=#008000]=====================================================================================================================[/color]
przez kokosek » Śr lis 11, 2009 8:22 pm
Masz za dużą złożoność czasową (chyba O(n^2) - czyli kwadratową).
Radzę to zrobić sitem Eratostenesa (znajdziesz je na wikipedii).
[color=#008000]=====================================================================================================================[/color]
przez kuszi » Śr cze 06, 2007 12:26 am
Masz zły warunek na to, czy liczba jest pierwsza. Mogą też być inne błędy. Ponadto dla tego zadania algorytm jest zły. Jest dużo pytań o małe liczby, więc opłaca się zastosować sito Erastotenesa.
Jeszcze jedna uwaga: jeśli w treści zadania jest podane, że n<100000, to
nie trzeba tego sprawdzać. I na koniec prośba: jeśli prosisz o pomoc odnośnie kodu źródłowego, ułóż go w taki sposób, aby ułatwić jego przeczytanie.
pozdrawiam
kuszner
[color=#008000]=====================================================================================================================[/color]
Pomoże ktoś co tutaj jest źle? Tu będzie chyba jakiś mały błąd, ale znaleźć nie mogę. Proszę o pomoc.
include
include
int a,b,i;
int main()
{
for(i=1;i<3;i++)
{
cin>>a;
b=pow(a,2);
for(;b>1;b--)
{
if(a%b==0)
{
cout<<"\n TAK"< }
else
{
cout<<"\n NIE"< }
}
}return 0;
}
Źle jest w zasadzie "wszystko", usuń i zacznij od początku. Pamiętaj też że liczba danych wejściowych nie wynosi dokładnie 3 za każdym razem, jest różna, i podawana jako pierwsza liczba na wejściu
test
3
11
27
99
Daje 3x TAK, co jest naturalnie bzdurą (powinno być 3 x NIE. Zresztą poczytaj o "sicie Eratostenesa", będziesz miał dużo lepszy czas. A już na pewno wywal elsea pod którym jest TAK, potwierdzenie masz dawać dopiero jak wszystkie będą miały resztę z dzielnie różną od zera a nie tylko 2
15 days later
Masz w swoim kodzie jeszcze sporo błędów, więc jak będziesz miała problemy, z samodzielnym poprawieniem, wystarczy że się uśmiechniesz 
, to może Ci wyśle poprawiony twój kod na pw.
Błędy, jakie znalazłem:
Ta instrukcja, nie jest konieczna:
[bbone=cpp,2593]if (test<100000)[/bbone]
a dodatkowo tu jest błędna. zAMIEŃ na:
[bbone=cpp,2594]if (test <= 100000)[/bbone]
analogicznie
[bbone=cpp,2595] if (liczba <= 10000)[/bbone]
Ta instrukcja:
[bbone=cpp,2596] else if(liczba==2||3)[/bbone]
powinna być zapisana:
[bbone=cpp,2597] else if(liczba == 2 || liczba == 3)[/bbone]
ale będzie u Ciebi działać, bo warunek zawsze jest true, i tak naprawdę u Ciebie, zadziała też samo else [inne warunki są już rozpatrzone wcześniej:
[bbone=cpp,2598] else
{
cout << "TAK\n";
}
[/bbone]
No i najważniejsze, musisz poprawić główną pętlę samego sprawdzania.
Witam.
Chciałbym poprosić o wskazówkę, gdzie popełniłem błąd.
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
static const auto max_test = 100000;
void print(std::vector<int> _v)
{
for (auto&& x : _v)
{
auto flag = true;
if (x < 2)
{
std::cout << "NIE\n";
flag = false;
continue;
}
for (int i = 2; i*i <= x; i++)
{
if (x%i == 0)
{
std::cout << "NIE\n";
flag = false;
continue;
}
}
if(flag)
std::cout << "TAK\n";
}
}
int main()
{
int x;
std::cin >> x;
std::vector<int> v;
if (x < max_test)
{
int y;
for (int i = 0; i < x; ++i)
{
std::cin >> y;
if(1 <= x && x <= 10000)
v.push_back(y);
}
print(v);
}
return 0;
}Z góry dziękuję za podpowiedź.
25 days later
Ok @krystian dzieki.
male moje niedopatrzenie w tym programie powodowalo ze w szczegolnym przypadku ten program nie dzialal poprawnie.
Po malej korekcji program zostal zaliczony:P
Mam problem z powyższym kodem mógłby ktoś rzucić okiem i dać jakąś uwagę na co zwrócić uwagę czy cały jest zły ? Wyskakuje błąd przekroczenia czasu połączenia 
8 days later
unsigned short inputCout = 0;to zbyt niska pojemność jak na 100000 testów, daj zwykłego inta i usuń kod z forum bo będzie AC.
ps za zgodność testów opisem w zadaniu odpowiada ich autor, nie musisz ich sprawdzać.
1) Program powinien wypisywać TAK i NIE, "sędziuje" program porównujący pliki więc wielkość liter jest ważna
2) Może być 100000 testów, podczas gdy ty masz tablicę tylko na 10000.
3) Za zgodność wejścia z specyfikacją w zadaniu odpowiada twórca testów, nie musisz tego sprawdzać. Ze względu na błąd z punktu drugiego to była jedna z przyczyn nie zaliczenia.
Po poprawieniu punktów 1 i 2 dostałem AC, więc usuń kod z forum
2 months later
1 month later
Witam mam prośbę o pomoc lub udzielenie wskazówki nad poprawą programu. Program działa poprawnie, sędzia go zaakceptową, jednak chciałbym w nim poprawić to żeby pozbyć się breaków oraz zmienić pętlę nieskończoną.
kod programu:
#include <iostream>
using namespace std;
int main()
{
int testy, n, pomocnicza;
cin >> testy;
for(int i=0; i<testy; i++)
{
cin >> n;
pomocnicza = 2;
for( ; ; )
{
if (pomocnicza == n)
{
cout << "TAK" << endl; break;
}
else if(0 == n%pomocnicza)
{
cout << "NIE" << endl; break;
}
else if(n<2)
{
cout << "NIE" << endl; break;
}
pomocnicza++;
}
}
return 0;
}Po pierwsze nie dajemy tu działających kodów, po drugie jak chcesz go znacznie przyśpieszyć, to zwróć się z pomocą do pana Eratostenesa
23 days later
