438. Liczby Pierwsze [PRIME_T]

kamil1001 · Jan '10

Oto mój kod:

#include <iostream>
#include <cmath>
using namespace std;
int main(int argc, char *argv[])
{
    long int n;
    cin>>n;
    long double liczba[n];
    for (int i=0; i<n; i++)
{
    cin>>liczba[i];
}

for (int i=0; i<n; i++){
if (liczba[i]>17)
{
    if (fmodl(liczba[i], 2)==0||fmodl(liczba[i], 3)==0||fmodl(liczba[i], 5)==0||fmodl(liczba[i], 7)==0||fmodl(liczba[i], 11)==0||fmodl(liczba[i], 13)==0||fmodl(liczba[i], 17)==0) cout<<"NIE"<<endl;
    else cout<<"TAK"<<endl;
}
else
{
if (liczba[i]==2||liczba[i]==3||liczba[i]==5||liczba[i]==7||liczba[i]==11||liczba[i]==13||liczba[i]==17) cout<<"TAK"<<endl;
else cout<<"NIE"<<endl;
}   
}
}

Z mojej wiedzy matematycznej wynika (no przecież każdą liczbę złożoną można przedstawić jako iloczyn liczb pierwszych), że program jest poprawny, a mimo to nie akceptuje mi tego rozwiązania

EDIT: Poczytałem sobie trochę o tym i już wiem co jest źle... Są liczby które mają małe liczby w rozkładzie na czynniki, ale może się trafić taka liczba, która ma duże dzielnii, ale z drugiej strony znalazłem na wikipedii (pl.wikipedia.org/wiki/Test_Millera-Rabina60) test, apod nim zapis, że dla liczb poniżej 341,550,071,728,321 trzeba sprawdzić tylko 2,3,5,7,11,13,17... To niestety nie działa. Jaki proponujecie Algorytm?

m_sasinowski1 · Jan '10

Gdybyś zaimplementował Rabina-Millera to by pewnie działało...

kamil1001 · Jan '10

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;
}

kokosek_sof1 · May '11

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)

narbej · Feb '15

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]

w0j0pl · Feb '15

Pomoże ktoś co tutaj jest źle? Tu będzie chyba jakiś mały błąd, ale znaleźć nie mogę. Proszę o pomoc.

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;
}

sig · Feb '15

Ź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

sig · Feb '15

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

anka12 · Mar '15

Bardzo dziękuję zarówno za podpowiedzi co do kodu (do wszystkiego się zastosuje) jak i za życzenia

narbej · Mar '15

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.

CA500_sof · Mar '15

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ź.

polsky · Apr '15

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

marison · Apr '15

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

sig · Apr '15

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ć.

miloszimazik · Apr '15

Witam,
Nie mogę sobie poradzić z sędzią... Co robię źle? Dla liczb które sprawdzałem zawsze działa

sig · Apr '15

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

tdudzik · Jul '15

Edytowane, bo nie przeniesiono tu postu do którego mój post się odnosił.

pacieciak · Sep '15

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;
}

sig · Sep '15

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

sig · Sep '15

Skoro znalazłeś błąd, to usuń kod z forum.

438. Liczby Pierwsze [PRIME_T]

created

last reply

replies

views

users

likes

links

Frequent Posters

Popular Links

include

include

309	SPOJ.com - Problem PRIME_T pl.spoj.com
60	Test Millera-Rabina – Wikipedia, wolna encyklopedia pl.wikipedia.org
54	Podstawy Programowania (SPOJ) spoj.com
40	SPOJ.com - Problem PTEST pl.spoj.com
31	https://www.spoj.pl/problems/PON/

438. Liczby Pierwsze [PRIME_T]

created

last reply

replies

views

users

likes

links

Frequent Posters

Popular Links

include

include

share a link to this topic