kwadrat liczby pierwszej

0

Program który wczyta n>0 a następnie wyznaczy i wydrukuje na ekranie liczby mniejsze od n, które są podzielne przez kwadrat dowolnej liczby pierwszej.
Bardzo proszę o pomoc w tym zadaniu i o jakieś wskazówki.

0

Pokaż co już masz

0

"podzielne przez kwadrat dowolnej liczby pierwszej" - nie rozumiem o co chodzi, mogłby Pan podać przykład jakis?

1

wypisz sobie na ekranie wszystkie kwadraty liczb pierwszych mniejszych niż miliard i zobacz jak tego jest mało. potem wypisz w postaci tablicy, wklej do kodu i zrób for loopa - masz rozwiązanie.

EDIT: tak jak kolega napisał pod spodem, jest ich jednak trochę więcej niż myślałem. Nadal zrobiłbym tablice wszystkich możliwych liczb pierwszych po czym zaczął od wersji która po prostu przechodzi przez wszystkie te liczby dla każdej z liczb które sprawdzasz.
Jeśli okaże się za wolne to proponuje zrobić dużą tablicę booli (dla wszystkich branych pod uwagę rozwiązań) i przejść po każdej liczbie pierwszej i zaznaczać wielkorotności kwadratów (coś podobnego do sita erastotenesa) i na końcu wypisać tylko zaznaczone liczby.

Generalnie problem jest podobny do rozkładu na czynniki pierwsze gdzie szukasz potęg czynników >= 2. W zależności na jakim zakresie operujesz trzeba inaczej podejść do problemu

0

Wciąż nie rozumiem, liczby pierwsze potrafię wypisac ale wypisać podzielne przez kwadrat dowolnej liczby już nie

0
Chory Pomidor napisał(a):

Wciąż nie rozumiem, liczby pierwsze potrafię wypisac ale wypisać podzielne przez kwadrat dowolnej liczby już nie

No jak potrafisz wypisać liczby pierwsze, to -- jak już tu mówiono, ale może nie tak wprost:

  • dla każdej liczby i od 1 do n-1:
  • dla każdej liczby pierwszej p mniejszej od i:
    • jeśli i dzieli się przez (p*p) to drukujesz i i kończysz wewnętrzną pętlę (break)
0

edytowałem odpowiedź jako że nieprzemyślałem pierwszego rozwiązania (zadziała tylko dla małych N). Wiesz jakie jest max N? (10^6; 10^9; 10^100?) Jest jakiś limit czasowy? Wielowątkowo czy jeden wątek?

0
krwq napisał(a):

edytowałem odpowiedź jako że nieprzemyślałem pierwszego rozwiązania (zadziała tylko dla małych N). Wiesz jakie jest max N? (10^6; 10^9; 10^100?) Jest jakiś limit czasowy? Wielowątkowo czy jeden wątek?

Nie, no dla N całkowitych mieszczących się na 8 bajtach to nie będzie tego wiele -- można zrobić taką tabelę statycznie (jak pisałeś), albo wygenerować z sita Eratostenesa. I z racji, że kwadrat, to wystarczy poszukać pierwszych tylko do pierwiastek(N).

0
#include <iostream>
#include<math.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int k=2;
    while(n>1)
    {
        while(n%k==0)
        {
            cout<<k<< " ";
            n/=k;
        }
        k++;
    }

    return 0;
}

na razie mam cos takiego i nie wiem jak to dalej ugryzc, proszę o pomoc.

1 użytkowników online, w tym zalogowanych: 0, gości: 1