• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Liczby pierwsze c++

VPS Starter Arubacloud
0 głosów
5,946 wizyt
pytanie zadane 11 listopada 2017 w C i C++ przez Scypyon Gaduła (3,450 p.)

Mam napisać program, który sprawdzi podane liczby i napisze czy są pierwsze

np. 3 2 5 7 1 ->>>> NIE TAK NIE TAK TAK

#include <iostream>

using namespace std;
int liczba[100];
int a,c=0;

int main()
{
    cin>>a;
    for(int i=0;i<a;i++)
    {
        cin>>liczba[i];
    }

    for(int j=0;j<a;j++)
    {

        for(int p=0;p*p<=liczba[c];p++)
        {
            if(liczba[c]<=2)
            {
                cout<<"TAK"<<endl;
                c++;
            }
            else if(liczba[c]%p==0)
            {
                cout<<"NIE"<<endl;
                c++;
            }
            else
            {
                cout<<"TAK"<<endl;
                c++;
            }
        }
    }

    return 0;
}

a to jest u mnie liczba tych liczb, wydaje mi się ,że źle rozumuje tablice i źle je inicjuje , mógłby mi ktoś to wytłumaczyć?

komentarz 11 listopada 2017 przez Milesq Nałogowiec (32,020 p.)
3 to liczba pierwsza podobnie 5

z kolei 1 nie jest nią
1
komentarz 11 listopada 2017 przez mokrowski Mędrzec (155,460 p.)
main czy spoj ? Bo mam wrażenie że gdzieś już widziałem to zadanie :-)
komentarz 13 listopada 2017 przez Scypyon Gaduła (3,450 p.)
spoj :)

3 odpowiedzi

0 głosów
odpowiedź 11 listopada 2017 przez michal12334 Obywatel (1,510 p.)
Tablica liczba ma 100 komórek o indeksach od 0 do 99. Jeśli a będzie większe niż 100 wtedy ta tablica będzie miała za mało komórek. Możesz zrobić to tak, że po podaniu liczby a dopiero tworzysz tablicę.
komentarz 11 listopada 2017 przez niezalogowany
* jeśli a będzie większe od 99.
komentarz 11 listopada 2017 przez michal12334 Obywatel (1,510 p.)
Nie bo  pętla wczytująca liczby wygląda tak for(int i=0;i<a;i++) czyli i=99 będzie ostatnim wykonaniem pętli dla a = 100, więc a może być równe 100, ale nie może być większe.
0 głosów
odpowiedź 11 listopada 2017 przez Aisekai Nałogowiec (42,190 p.)
edycja 11 listopada 2017 przez Aisekai
Najpierw sprawdź sobie czym są liczby pierwsze. Liczba pierwsza to liczba która dzieli się bez reszty przez 1 i przez siebie. Ale te dwa dzielniki muszą być różne.  Jeżeli liczba<=2 nie znaczy że jest liczbą pierwszą albo nie jest. Bo: liczba 0 i 1 nie jest liczbą pierwszą, natomiast 2 już tak. Nie masz sprawdzać które liczby dzielą twoją liczbę, tylko czy jest liczbą pierwszą.

Więc: najpierw wczytujesz jakieś liczby do tablicy. Potem dla każdego elementu sprawdzasz czy dzieli go jeszcze jakaś inna liczba niż 1 i ta liczba (pamiętając, że 2 jest liczbą pierwszą, natomiast każda jej wielokrotność (liczby parzyste) już nie są liczbami pierwszymi). Jeżeli dzieli, to wychodzisz z pętli to wyświetlasz że NIE i przechodzisz do kolejnej iteracji pętli (continue outerloop). Na końcu tej pierwszej pętli wyświetl TAK. Wyświetli tak, jeśli przejdzie przez pętlę sprawdzającą czy liczba jest liczbą pierwszą. Jeżeli by gdzieś się znalazła taka liczba która by dzieliła twoją liczbę, to przejdzie do kolejnej iteracji. Jeżeli by nie znalazło to opuści pętlę i wyświetli TAK.

 

Jak już coś takiego zrobisz, to potem możesz poczytać o sicie erastotensa i zrobić to wykorzystując ten algorytm. Przy czym, będziesz potrzebował znać max w tablicy, żeby móc zrobić to zadanie.

edit: Do przechowywania nieokreślonej liczby danych, lepiej używać jakichś dynamicznych struktur. Jeżeli chcesz to robić na niedynamicznych, musiałbyś najpierw poprosić użytkownika o podanie ilości danych. Bo ty zakładasz, że danych będzie max 100.
komentarz 11 listopada 2017 przez Scypyon Gaduła (3,450 p.)
właśnie z tego co czytałem to teoretycznie nie można zrobić tablicy, która będzie przechowywała tyle zmiennych co poda użytkownik  ale ponoć da się to obejść, za bibliotekę vector nie mam ochoty się zabierać, mógłbyś mi podesłać jakiś rzetelny poradnik dotyczący tych dynamicznych struktur ?
komentarz 11 listopada 2017 przez Scypyon Gaduła (3,450 p.)
for(int p=0;p*p<=liczba[c];p++)
        {
            if(liczba[c]<=1)
            {
                cout<<"NIE"<<endl;
                c++;
            }
            else if(liczba[c]==2)
            {
                cout<<"TAK"<<endl;
                c++;
            }
            else if(liczba[c]%p==0)
            {
                cout<<"NIE"<<endl;
                c++;
            }
            else
            {
                cout<<"TAK"<<endl;
                c++;
            }

zmieniłem tak warunki i np dla wartości: 2/2/2 wyświetla mi TAK/TAK/NIE ,a powinno tylko TAK/TAK,czyli mówisz ,że moje rozumowanie jest błędne i powinienem od nowa to zrobić?

komentarz 11 listopada 2017 przez Aisekai Nałogowiec (42,190 p.)
Do vectora da się podawać tyle liczb ile użytkownik poda, o ile pamięć na to pozwoli i o ile założysz (w konsoli) jakąś opcję (np że najpierw dodaje, a potem się go pytasz czy chce jeszcze dodać).. Zrób program od początku. Albo poszukaj na internecie program który sprawdza czy liczba jest pierwszą i go przerób. Ale spróbuj go najpierw zrozumieć.

Ta pętla for(int p=0;p*p<=liczba[c];p++) powinna wypisywać NIE jeśli nie jest liczbą pierwszą i rozpocząć następną iterację, a jeżeli wyjdzie z tej pętli (czyli będzie liczbą pierwszą) niech wyświetli TAK. Poczytaj o continue i outerloop.

Edit: jeżeli chcesz się uczyć C++ to prędzej czy później vector Cię nie ominie
komentarz 11 listopada 2017 przez Nk_1 Nowicjusz (140 p.)
edycja 3 kwietnia 2018 przez Nk_1

Może przyda się inny sposób analizy liczb pierwszych pokazany poniżej. Pozwala na większy zakres analizy liczb pierwszych w Excelu.

Sito Małgorzaty opisane pod linkiem: https://1drv.ms/b/s!AsqwpKK-51whhhzzvgOxdib8Y_rW

Sub sito()

    Dim j, i As Long
    Dim a, b As Long
    Dim t As Boolean
    Dim f As Boolean
    Dim x_max As Long
    Dim x As Long
    Dim yp As Long
    
    Dim pk As Integer
    Dim pky As Integer
    Dim pk_max As Integer
    Dim pk_min As Integer
    
    Range("B:Z").ClearContents
    'ilo栤anych w kadej kolumnie
    x_max = Range("A1").Text
    'ilo栫olumn - warto栭ax 25
    pk_max = Range("A2").Text
    
    ' zaczynamy od 2 kolumny
    pk = 2
    pky = 2
    pk_min = 2
    pk_max = pk_max + 1
    t = True
   
    ' warto栰ocztkowa dla iteracji
    yp = 1
    i = 0

    Do
        i = i + 1
        ' warto栰ocztkowa x dla danej iteracji i
        x = yp
        ' wyliczenie wartosci a i b
        a = 1 + 2 * i
        If t Then
           b = 4 * i + 3
        Else
           b = 4 * i + 1
        End If
        ' ustawienie kolejnoci a czy b - t dla iteracji i , f dla poditeracji
        f = t
        If Cells(i, pk).Value <> 1 Then
          If f Then
            x = x + b
            yp = x + a
          Else
            x = x + a
            yp = x + b
          End If
          'zaznaczenie elementla danej iteracji
          For j = pk_min To pk_max
            Do While x < x_max
              Cells(x, j) = 1
              If f Then
                x = x + a
              Else
                x = x + b
              End If
              f = Not (f)
            Loop
            x = x - x_max + 1
          Next j
        Else
          yp = yp + a + b
        End If
        If Not (yp < x_max) Then
            yp = yp - x_max + 1
            pky = pky + 1
        End If
        pk_min = pky
        t = Not (t)
    Loop Until (pky > pk_max)

End Sub

0 głosów
odpowiedź 3 kwietnia 2018 przez Beginer Pasjonat (22,110 p.)
Dobrze "rozumujesz" tablicę, masz ją właściwie zainicjowaną. Tak w tym zadaniu należało postąpić.

Koledzy dokładnie przedstawili teorię liczb pierwszych. Pozostaje tylko właściwie postawić warunki, co nie jest trudne.

 

P.S. Nie pisz tak zwiężle kodu w poziomie - nie sklejaj znaków, rób spacje.
komentarz 3 kwietnia 2018 przez Toxxxiczny Początkujący (260 p.)

siemka, miałem zakaladc nowy temat ale widze ze tutaj odkopany troche laugh ii pytanko dotyczace nastepujacej linii kodu:

 if ( (i%liczby[1]==0) && (i%liczby[i]==0) && (i%liczby[a!=1]!=0) && (i%liczby[a!=i]!=0) )
        {
            cout<<"Podzielna tylko przez 1 i przez siebie"<<endl;
        }

wyskakuje błąd "forbids comparison between pointer and integer"

a warunek na liczbe pierwsza wymysliłem tak że najpierw 

-gdy podzielna przez 1 bez reszty

-gdy podzielna bez reszty przez sama siebie no to liczby[i]

-I TUTAJ : gdy podzielna z resztą, przez liczby różne od 1

-I gdy podzielna z resztą, przez liczby różne od aktualnej iteracji 

Pytanie czy dobrze to ująłem, z gory dzieki za pomoc 

cały kod: 

#include <iostream>
using namespace std;
int main()
{
       int liczby[101];
    for(int i=0; i<101; i++)
    {
        liczby[i]=i;
    }

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

    for(int i=1; i<101; i++)
    {

        cout<<"Liczba: "<<i<<endl;
        if ( (i%liczby[1]==0) && (i%liczby[i]==0) && (i%liczby[a!=1]!=0) && (i%liczby[a!=i]!=0) )
        {
            cout<<"Podzielna tylko przez 1 i przez siebie"<<endl;
        }
    }
}

 

komentarz 3 kwietnia 2018 przez Beginer Pasjonat (22,110 p.)
Co do zasady dobrze postawiłeś warunki, ale spróbuj jeszcze uprościć zadanie.

- liczbami: 0, 1 nie warto się zajmować (sprawdzać), bo nie są liczbami pierwszymi;

- liczby: 2, 3, 5, 7 wiadomo, że są liczbami pierwszymi. Sprawdzanie (iterowanie) można zacząć od razu od liczby 11.

- zamiast dzielić kolejno przez wszystkie n-liczb, wystarczy sprawdzać czy bieżąca liczba dzieli się bez reszty przez: 2, lub 3, lub 5, lub 7. Wtedy nie jest liczbą pierwszą.
komentarz 3 kwietnia 2018 przez mokrowski Mędrzec (155,460 p.)

@Toxxxiczny, zadanie ze SPOJ'a wykonasz bez alokowania tablicy. Wystarczy liczbę sprawdzić tuż po wczytaniu i zwrócić TAK lub NIE.

komentarz 3 kwietnia 2018 przez Toxxxiczny Początkujący (260 p.)
Hmm czy probowaleś u Siebie odpalić kod? Jesli warunek dobrze postawilem to co moze byc źle że wyskakuje błąd :/ do wskaznikow jeszcze nie dotarłem ale wiem że oznacza sie je "*" i postawilem gwiazdkę przed "a" w tym 3 warunku i coś jest nie tak z programem :p
komentarz 3 kwietnia 2018 przez Toxxxiczny Początkujący (260 p.)

@mokrowski, akurat nie robie ze spoja zadań narazie ale dzięki za info doceniam ;)

komentarz 3 kwietnia 2018 przez Beginer Pasjonat (22,110 p.)

Liczba jest pierwszą, jeśli dzieli się wyłącznie przez 1 i przez samą siebie.

P.S. Tablica jest niepotrzebna.

komentarz 17 lipca 2019 przez Nk_1 Nowicjusz (140 p.)
Ciekawostka: liczby pierwsze można prosto wyznaczać za pomocną fraktala Rafała, który można opisać wzorem:
f(y)= n + x * (-1)^{n} + (3*x + 0.5 - 0.5 * (-1)^{x}) * (n + 0.5 - 0.5 * (-1)^{n})
gdzie n > 0 i x >0 oraz x,n należy do liczb naturalnych. Liczba x określa kolejne wystąpienie liczby "złożonej" dla n. Dodatkowo zachodzi zależność jezeli:
x parzyste, n parzyste to f(y) parzyste
x parzyste, n nieparzyste to f(y) nieparzyste
x nieparzyste, n parzyste to f(y) nieparzyste
x nieparzyste, n nieparzyste to f(y) parzyste

Związek liczb złożonych z fraktalem Rafała jest następujący:
f(z)= 3 * f(y) + 1.5 - 0.5 *(-1)^{x+n}
gdzie f(y) funkcja generująca liczby tworzące fraktal Rafał dla wartości x i n.

Jeżeli dla wzoru f(y) wprowadzimy ograniczenie x >= n oraz f(y) <= Ym to otrzymamy tzw. sito Małgorzaty w przedziale liczb naturalnych (1,Ym).
Związek wartości Y z przedziału (1,Ym) z liczbami (złożonymi i pierwszymi) jest następujący:
f(L)= 3 * Y + 2 dla wartości nieparzystych Y lub
f(L)= 3 * Y + 1 dla wartości parzystych Y
oraz f(L) jest liczbą złożoną jeżeli wartość Y została wyznaczona przez f(y).
komentarz 14 października 2019 przez Nk_1 Nowicjusz (140 p.)
edycja 14 października 2019 przez Nk_1
Jak już pisałem fraktal Rafała można opisać wzorem:
    f(y)= n + x * (-1)^{n} + (3*x + 0.5 - 0.5 * (-1)^{x}) * (n + 0.5 - 0.5 * (-1)^{n})
gdzie n > 0 i x >0 oraz x, n należy do liczb naturalnych.

 W celu ułatwienia zrozumienia dalszej analizy zrobię małe podsumowanie:
1)    Sito Małgorzaty to fraktal Rafała przy założeniu, że x>=n oraz f(y) <Ym
gdzie Ym wyznacza górną granicę sita tj. wartości  f(y) należą do przedziału (1,Ym).
Dodatkowo dla n=f(yn) dla dowolnego x wartości f(y) można pominąć – nie mają
wpływu na wynik sita, a jedynie wykonuje się mniej obliczeń.
2)    Dla wartości f(y) fraktala Rafała zachodzą zależności:
   - x parzyste, n parzyste to f(y) parzyste
   - x parzyste, n nieparzyste to f(y) nieparzyste
   - x nieparzyste, n parzyste to f(y) nieparzyste
   - x nieparzyste, n nieparzyste to f(y) parzyste
Poszczególne warianty sita liczb będą tworzone poprzez branie do dalszej
analizy parzystych lub nieparzystych wierszy tabeli:
wiersze (1,Ys), kolumny n.
(n powiązane z Ly – Ly=3 * n + 1,5 – 0,5 * (-1)^n)
3)    Szczególną uwagę można zwrócić na wynik działania fraktal Rafała dla n=1 i n=2
dla dowolnego x. W analizie posłuży to do wyliczenia „podstawy” wyznaczenia różnych wariantów sita liczb.
4)    Analizowane będą różne warianty sita liczb – dające wartość f(ys) w przedziale
(1,Ys). Jeżeli związek pomiędzy wartościami ys a y (zależny jest od wyboru wierszy parzystych i nieparzystych tabeli wspomnianej w punkcie 2) określimy jako funkcję y=P(ys), to wartości ys z przedziału (1,Ys) z liczbami (złożonymi i pierwszymi) dla każdego wariantu sita liczb można zapisać ogólnie:
f(L)= 3 * P(ys) + 2 dla wartości nieparzystych  P(ys) lub
f(L)= 3 * P(ys) + 1 dla wartości parzystych P(ys)
oraz f(L) jest liczbą złożoną jeżeli wartość ys została wyznaczona przez f(ys).

Korzystając z możliwości wyboru wierszy parzystych (sito_p) lub nieparzystych  (sito_n) tworzymy dwa niezależne sita liczb. Dalsze przetwarzanie i analiza sita liczb w obu przypadkach jest podoba:
  - dla każdej kolumny n mamy pierwszą wyznaczoną wartość ys1,
    którą można określić jako podstawa;
  - pozostałe wartości dla kolumny n są  w odległości Ly
    (Ly=3 * n + 1,5 – 0,5 * (-1)^n).

Jeżeli dla jednego z wybranych sit liczb zaczniemy znowu wybierać wiersze parzyste i nieparzyste tworzymy kolejny wariant sita liczb. Powtarzając tę czynność  można tworzyć kolejne sita liczb. Zauważyć można, że tak tworzone sito licz zawiera w kolumnie n pierwszą wartość ys1, którą można nazwać podstawą tworzenia sita. Pozostałe wartości w kolumnie n są zawsze w odległości Ly.
Dodatkowo jeżeli wartość ys1 ma być uwzględniona w docelowy sicie liczb, a jest w odrzucanych wierszach, to bierzemy ys1+Ly jako podstawę do kolejnego sita.

Jako ciekawostkę mogę podać sito liczb utworzone poprzez trzykrotnie wybranie parzystych wierszy. Jego zaletą jest to, że wyrazy ys1  dla kolejnych kolumn n tworzą ciąg, którego elementy różnią się o wartość n/(1,5 + 0,5 * (-1)^n) oraz wyrazy ys1 odpowiadają kwadratom liczb Ly. Pozostałe wartości ys w danej kolumnie są w odległości Ly.
komentarz 20 listopada 2020 przez Nk_1 Nowicjusz (140 p.)
edycja 20 listopada 2020 przez Nk_1

W nawiązaniu do wyżej zamieszczonych informacji chciałem zaprezentować ciekawą tabelę. Zdefinujmy tabelę Y mającą k kolumn i w wierszy. Wartości k, w należą do liczb naturalnych oraz k > 0 i w > 0. Wybrany element tabeli będziemy oznaczać Y[w,k]. 

Dodatkowo zdefinujmy liczbę Lyw taką, że:

Lyw =3*w+1,5 - 0,5*(-1)^w

tj. dla w parzystych Lyw= 3*w+1 a dla w nieparzystych Lyw=3*w+2

Dla wartości k=1 elementy Y[w,1] przyjmują wartości:

dla w parzyste Y[w,1] = w+1 a dla w nieparzyste Y[w,1] = (w+1)*2

Natomiast  dla wartości k>1 elementy Y[w,k] przyjmują wartości:

dla Y[w,k-1] parzyste i k parzyste                Y[w,k] = (Y[w,k-1] + 1 + Lyw)/2

dla Y[w,k-1] nieparzyste i k parzyste           Y[w,k] = (Y[w,k-1] + 1)/2

dla Y[w,k-1] parzyste i k nieparzyste           Y[w,k] = Y[w,k-1]/2

dla Y[w,k-1] nieparzyste i k nieparzyste      Y[w,k] = (Y[w,k-1] + Lyw)/2

Przy tak zdefiniowanej tabeli Y, wprowadźmy jeszcze jedną liczbę:

Mk = 2^k - 1, gdzie k > 2

dodatkowo jeżeli k będzie liczbą pierwszą oraz Y[w,k] różne  od  1 dla w <= (Mk-1)/6, to ze 100% pewnością można powiedzieć, że liczba Mk dla danego k jest liczbą pierwszą.

Okazuje się też, że wartości Y[w,k] dla danego w powtarzają się okresowo w odstępach mniejszych lub równych Lyw-1.

Podobne pytania

0 głosów
3 odpowiedzi 911 wizyt
pytanie zadane 28 kwietnia 2017 w C i C++ przez seba Dyskutant (8,900 p.)
0 głosów
1 odpowiedź 2,287 wizyt
0 głosów
0 odpowiedzi 189 wizyt
pytanie zadane 1 sierpnia 2023 w C i C++ przez Jakub005 Początkujący (310 p.)

92,455 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...