Zbiór Zadań od CKE zad 59.1

pytanie zadane 12 kwietnia 2018 w C i C++ przez Scypyon Gaduła (3,450 p.)

Treść:

59.1.

Czynnikiem pierwszym danej liczby naturalnej złożonej jest dowolna liczba pierwsza, która dzieli tę liczbę całkowicie. Podaj, ile jest w pliku liczby.txt liczb, w których rozkładzie na czynniki pierwsze występują dokładnie trzy różne czynniki (mogą się one powtarzać, z których każdy jest nieparzysty.

Przykład

Liczba	Czynniki pierwsze	Czy w rozkładzie występują dokładnie trzy różne nieparzyste czynniki pierwsze?
32	2, 2, 2, 2, 2	NIE
210	2, 3, 5, 7	NIE
1331	11, 11, 11	NIE
1157625	3, 3, 3, 5, 5, 5, 7, 7, 7	TAK
105	3, 5, 7	TAK
429	3, 11, 13	TAK
1287	3, 3, 11, 13	TAK
3465	3, 3, 5, 7, 11	NIE
255255	3, 5, 7, 11, 13, 17	NIE

#include <iostream>
#include <math.h>
#include <sstream>
#include <fstream>

using namespace std;

int czy_trzy(int liczba)
{
    int z = 0;
    int i = 2;

    while(liczba>0)
    {
        if(liczba%i==0)liczba=liczba/2;
        else
        {
            i++;
            continue;
        }
        int w=0;
        for(int j=1;i>=j;j++)
        {
            if((i>2)&&(i%j==0))w++;
        }
        if(w==2)z++;
    }
    if(z==3) return 1;
    else return 0;
}
int main()
{
    fstream plik;
    plik.open("liczby.txt", ios::out|ios::in);

    int liczba;
    int zad1 = 0;

    while(!plik.eof())
    {
        plik>>liczba;
        zad1+=czy_trzy(liczba);
    }
    cout<<"Wynik zad1: "<<zad1<<endl;

    return 0;
}

Program się kompiluje jednak nie wyrzuca wyniku , nie mam pojęcia co robię źle :/

+ nie mam pojęcia jak mogę spełnić warunek "Trzy różne" mój program sprawdza czy ma 3 czynniki pierwsze, ale nie czy są różne

3 odpowiedzi

odpowiedź 13 kwietnia 2018 przez mokrowski Mędrzec (155,460 p.)
wybrane 15 kwietnia 2018 przez Scypyon

Najlepsza

nie mam pojęcia jak mogę spełnić warunek "Trzy różne" mój program sprawdza czy ma 3 czynniki pierwsze, ale nie czy są różne

Kontenerem który umożliwia "gromadzenie unikalnych wartości" jest std::set. Jeśli dodasz do niego dzielniki, na końcu możesz sprawdzić .size(). Jeśli zwróci 3, tzn. że są unikalne 3 wartości.

Test czy liczba jest pierwsza możesz przeprowadzić bez konsumpcji dużej ilości pamięci tak:

bool isPrime(int num) {
    if (num <= 3) {
        return num > 1;
    } else if ((num % 2 == 0) || (num % 3 == 0)) {
        return false;
    } else {
        for (int i = 5; i * i <= num; i += 6) {
            if ((num % i == 0) || (num % (i + 2) == 0)) {
                return false;
            }
        }
        return true;
    }
}

Można oczywiście iterować do pierwiastka. Niemniej jednak mnożenie jest szybsze dla liczb które nie są float. Kompilator jednak sam się zorientuje że wartość jest stała.

Informacja że czynnik jest nieparzysty, sugeruje krok sprawdzania 2 od wartości nieparzystej.

Masz trochę "niezgrabności" w obsłudze pliku..

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

Pisz klamry jak w C++. Please.

(Lepiej wszystko widać)

komentarz 13 kwietnia 2018 przez mokrowski Mędrzec (155,460 p.)

Chcesz zgodne z MISRA czy problem z priorytetami operatorów?

komentarz 13 kwietnia 2018 przez Scypyon Gaduła (3,450 p.)

Kompletnie nie rozumiem co się tutaj dzieje, :/

komentarz 13 kwietnia 2018 przez mokrowski Mędrzec (155,460 p.)

Linia 2-3 załatwia zwrócenie wartości true dla liczb 2 i 3 które są pierwsze.

Linia 4-5 sprawdza czy liczba jest podzielna przez 2 lub 3. Jeśli jest zwraca false bo liczba nie jest pierwsza.

Linia 7-12, nie ma rady. Sprawdzamy pracowicie czy jest pierwsza. Zaczynam od 5 bo wcześniejsze warunki problem załatwiły dla liczb mniejszych niż 5. Idę z krokiem 6 bo wcześniej sprawdziłem dzielenie przez 2 i 3. Kończę na wartości pierwiastka z liczby bo powyżej z całą pewnością nie ma dzielników. Żeby nie liczyć pierwiastka (bo to kosztowne), sprawdzam potęgę 2 dzielnika czy nie jest większa niż liczba.

Linie 8-9 sprawdzają pracowicie czy liczba dzieli się przez potencjalny dzielnik bez reszty.

To jest trochę bardziej zoptymalizowany kod i stosunkowo szybki (nie najszybszy). Konsumuje mało pamięci w przeciwieństwie do sita Eratostenesa https://pl.wikipedia.org/wiki/Sito_Eratostenesa .

Jeszcze szybszą metodą jest proponowana przez Bernsteina (kryptoanalityk i autor qmail'a i bezpiecznych serwisów sieciowych). Ale to już trochę więcej wiedzy http://cr.yp.to/primetests.html

komentarz 13 kwietnia 2018 przez Scypyon Gaduła (3,450 p.)

To jest w standardzie cpp 11 ?

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

Bez obaw. To jest funkcja w stylu "Hello world!" - nie ma żadnych wymagań.

komentarz 14 kwietnia 2018 przez Scypyon Gaduła (3,450 p.)

zrobiłem tak:

bool spr(int liczba)
{
    int ilosc=0;
    int dod =0;
    if(liczba%2==0)
    {
        return false;
    }

    for(int i=3;i<=liczba;i+=2)
    {
        while(liczba%i==0)
        {
            liczba/=i;
            dod++;
        }
        if(dod>0)
            ilosc++;
        dod=0;

        if(liczba==1)
            break;

    }
if(ilosc==3)
    return true;
else
    return false;


}

Dzięki za pomoc :) daje naj

odpowiedź 12 kwietnia 2018 przez Beginer Pasjonat (22,110 p.)

To nie jest zupełnie proste zadanie (w sensie napisania kodu). Mam wrażenie, że chciałeś je zrobić za prosto. Dużo rzeczy zrobiłeś już dobrze, ale część nie. Na przykład szukając kolejnych czynników program dzieli liczbę także przez l.parzyste 4, 6, 8 Itd. One są zbędne, ponieważ nie są czynnikami pierwszymi.

Program musisz uruchomić etapami. Na początku napisz / popraw funkcję, która będzie sprawnie dzielić liczbę na czynniki pierwsze - np.liczbę 32. Każdy znaleziony czynnik musisz pakować do niewielkiej tablicy albo kontenera.

komentarz 12 kwietnia 2018 przez Scypyon Gaduła (3,450 p.)

Na przykład szukając kolejnych czynników program dzieli liczbę także przez l.parzyste 4, 6, 8 Itd. One są zbędne, ponieważ nie są czynnikami pierwszymi.

Możesz rozwinąć? Przecież rozkład na czynniki to od najmniejszych(czyli 2) i dopóki liczba nie będzie równa 1, ja nigdzie nie zapisuje tych cyfr(tych które nie są czynnikami pierwszymi)

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

To dobrze, że nie zapisujesz. Ale również nie ma sensu ich sprawdzać (zabiera czas i wygląda "nie fachowo").

komentarz 12 kwietnia 2018 przez Scypyon Gaduła (3,450 p.)

Rozumiem co masz na myśli, jutro z rana na spokojnie jeszcze raz do tego podejdę i wstawię postępy :)

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

Może na początku programu utwórz tablicę z liczbami pierwszymi, np.

int liczby_pierwsze = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29);

I z tej tablicy pobieraj elementy do sprawdzania (dzielenia) badanej liczby.

Zauważ tylko, że liczby pierwsze nie kończą się na 29, ale dla potrzeb tego zadania może wystarczyć. W ogólnym przypadku powinno się zrobić jeszcze dodatkową funkcję do wyznaczania liczb pierwszych. (Ale nie ma co komplikować).

Może będziesz miał jakiś inny dobry patent.

P.S. Nawiasy przy tablicy powinny być sześcienne. (Nadaję z tabletu).

komentarz 13 kwietnia 2018 przez Scypyon Gaduła (3,450 p.)

#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int czy_trzy(int liczba)
{
    int i = 2;
    int dzielniki[50];
    int w = 0;
    int x = 0;

    if(liczba%2==0)
    {
       return 0;
    }
    else
    {
        while(liczba>1)
        {
            int z = 0;

            if(liczba%i==0)
            {
                liczba=liczba/i;
            }
            else
            {
                i++;
                continue;
            }
            for(int j=1;i>=j;j++)
            {
                if((i%j==0)&&(i>2))
                {
                    z++;
                }
            }
            if(z==2)
            {
                dzielniki[w]=i;
                w++;
            }
        }
        for(int a=0;w>a;a++)
        {
            if(dzielniki[a]!=dzielniki[a+1])x++;
        }
    }
    if(x==3)return 1;
    else return 0;
}

int main()
{
    fstream plik;

    plik.open("liczby.txt", ios::in | ios::out);

    int liczba;
    int b= 0;

    while(!plik.eof())
    {
        plik>>liczba;
        b+=czy_trzy(liczba);
    }
    cout<<"Wynik: "<<b<<endl;
    return 0;
}

Powinno działa, kompiluje się ale chyba za dużo pamięci pobiera :/

komentarz 13 kwietnia 2018 przez Aisekai Nałogowiec (42,190 p.)

Dzieli przez liczby parzyste, ale zauważ że jesli liczba jest parzysta np 6, to rozkłada się ona na czynniki pierwsze, mniejsze od 6. Więc, odpowiednio dobrze napisany program rozkladajacy liczbę na czynniki pierwsze, eliminuje sam liczby parzyste jako czynniki pierwsze, rozkładajac je wcześniej.

odpowiedź 16 kwietnia 2018 przez Scypyon Gaduła (3,450 p.)

#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int czy_trzy(int liczba)
{
    int i = 3;
    int dzielniki[50];
    int w = 0;
    int x = 0;

    if(liczba%2==0)
    {
       return 0;
    }
    else
    {
        while(liczba>1)
        {
            int z = 0;

            if(liczba%i==0)
            {
                liczba=liczba/i;
                dzielniki[w]=i;
                w++;
            }
            else
            {
                i=i+2;
                continue;
            }

        }
        for(int a=0;w>a;a++)
        {
            if(dzielniki[a]!=dzielniki[a+1])x++;
        }
    }
    if(x==3)return 1;
    else return 0;
}

int main()
{
    fstream plik;

    plik.open("liczby.txt", ios::in | ios::out);

    int liczba;
    int b= 0;

    while(!plik.eof())
    {
        plik>>liczba;

        b+=czy_trzy(liczba);
    }
    cout<<"Wynik: "<<b<<endl;
    return 0;
}

Ciekawostka, program kompiluje się 18sec, jeżeli sprawdzamy czy liczba jest pierwsza to 55sec, wszystko działało od początku prawie :)