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
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
iod1don-1: - dla każdej liczby pierwszej
pmniejszej odi:- jeśli
idzieli się przez(p*p)to drukujeszii kończysz wewnętrzną pętlę (break)
- jeśli
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.
0
to mi wygląda na pochodną tego tematu: https://4programmers.net/Forum/C_i_C++/302931-jezyk_c_spoj?p=1440246#id1440246
0
To będzie podobnie jak w Sicie Erastothenesa, tylko zmieniamy krok (co kwadrat liczby pierwszej) i odwracamy z True do False tablicę wynikową, pseudokod:
fun simple_sieve(n):
arr = [True] * n # Tablica boolean rozm n init do True
for i = 2 to int(sqrt(n)) + 1):
if arr[i] is True:
j = i*i
k = i # Krok co kwadrat liczby pierwszej
while j < n:
arr[j] = False
j = i * i + k * i
k += i # inkrementujemy krok
output = [] # deklaracja wynikowej arraylist (vector c++)
for i in range(2, len(arr)):
if arr[i] is False: # odwrócone do oryginalnego sita
output.append(i)
return output
print(simple_sieve(30)) # -> [4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28]
0
ale maja byc podzielne przez kwadrat dowolnej liczby pierwszej bo na razie daja kwadrat liczby pierwszej?
0
robertos18 napisał(a):
ale maja byc podzielne przez kwadrat dowolnej liczby pierwszej bo na razie daja kwadrat liczby pierwszej?
Serio?
Przecież liczb pierwszych jest nieskończoność...
I ich kwadraty mogą być też nieskończone cała esencja liczb pierwszych polega na tym, że się nie kończą....
0
robertos18 napisał(a):
ale maja byc podzielne przez kwadrat dowolnej liczby pierwszej bo na razie daja kwadrat liczby pierwszej?
Nie wiem co Widzisz, ale jak widzę co innego, nie testowałem tej funkcji dokładnie, ale dla, np., 30, jak powyżej daje dobry wynik: drukuje tylko te liczby, mniejsze od 30, które są podzielne przez kwadrat jakiejś liczby pierwszej (w tym wypadku 2, 3 i 5, gdyż przez wieksza nie jest to możliwe - 7 * 7 = 49 > 30)
0
Mógłbys zerknąć czy jest dobrze? :
#include <iostream>
using namespace std;
int main()
{
int n;
cout << "Wpisz n: ";
cin >> n;
bool *tab = new bool[n];
for(int i = 1; i <= n; i++)
{
tab[i] = true;
}
tab[1] = false;
for(int i = 1; i*i <= n; i++)
{
if(tab[i]==true)
{
for(int j=2*i; j<=n; j++)
{
if (j%i==0) tab[j]=false;
}
cout<<i<<" ";
}
}
return 0;
}
0
Pamiętam jak się jarałem, że umiem wszystko w pamięci obliczyć każde równanie, a tu się klops okazał, bo przy większych liczbach same liczby pierwsze wychodziły, które miały odpowiedniki po 10 miejsc po przecinku, gdzie 3 to było easy bo 33333333 po przecinku to pestka, 2 i 5 to lustrzane odbicia, a takie 7 o jpd 14 miejsc po przecinku i w głowie to można było tylko to zrobić...
0
robertos18 napisał(a):
Mógłbys zerknąć czy jest dobrze? :
#include <iostream> using namespace std; int main() { int n; cout << "Wpisz n: "; cin >> n; bool *tab = new bool[n]; for(int i = 1; i <= n; i++) { tab[i] = true; } tab[1] = false; for(int i = 1; i*i <= n; i++) { if(tab[i]==true) { for(int j=2*i; j<=n; j++) { if (j%i==0) tab[j]=false; } cout<<i<<" "; } } return 0; }
A działa Ci to? Czemu pozmieniałeś pętle while na for? Pierwsze for u mnie zaczyna się od 2 a nie od jeden: for(int i = 1; i*i <= n; i++)
0
po prostu jak dla mnie mało czytelny ten pseudokod jest
0
Jak to przepisać do C++, to wygląda tak i chyba działa:
int main(int argc, char **argv)
{
int n;
cout << "Wpisz n: ";
cin >> n;
bool *tab = new bool[n];
for(int i = 1; i <= n; i++)
{
tab[i] = true;
}
//tab[1] = false;
for(int i = 2; i*i <= n; i++)
{
if(tab[i]==true)
{
int j = i * i;
int k = i;
while (j < n) {
tab[j] = false;
j = i * i + k * i;
k += i;
}
}
}
for (int i = 2; i < n; i++ ){
if (! tab[i])
cout << i << ", ";
}
return 0;
}
0
eh wciąz nie rozumiem dlaczego dla 30 daje takie liczby [4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28]
Z czego to wynika?
0
@robertos18, 2^2 => wielokrotności to 4*{1,2,3,4,5...}, potem 3^3 => 9 * {1,2,3,4,5...} itd
0
robertos18 napisał(a):
eh wciąz nie rozumiem dlaczego dla 30 daje takie liczby [4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28]
Z czego to wynika?
Od tego się program pisze, żeby robił takie jajca jakie chcemy.
0
robertos18 napisał(a):
eh wciąz nie rozumiem dlaczego dla 30 daje takie liczby [4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28]
Z czego to wynika?
Przestudiuj sobie algorytm Sita Erasthotenesa, w skrocie, sito, Np, dla 2, wykresla 4, 6, 8, itd... A ja zmienilem krok z liczby I na I*I I umnie wykresla 4, 8, 12, ...itd, czyli to o co Ci chodzi. Podalem linka do wikipedii.