Wczyta z klawiatury liczbę całkowitą n i na standardowe wyjście wypisze

Odpowiedz Nowy wątek
2019-01-03 18:25

Rejestracja: 2 lata temu

Ostatnio: 11 miesięcy temu

0

Napisz program w języku C++, który wczyta z klawiatury liczbę całkowitą n i na standardowe wyjście wypisze:

n nie jest liczbą pierwszą – jeśli n nie jest pierwsza,
n jest liczbą pierwszą numer X – jeśli n jest liczbą pierwszą.

  1. Założenie: n >= 2 i n <= 50000.

  2. Aby rozwiązanie zostało zaakceptowane musi w nim wystąpić element indeksowania liczb pierwszych w tablicy. Preferowane jest wykorzystanie algorytmu sita Eratostenesa.

  3. Wartości "n", "X" na wyjściu należy oczywiście zastąpić odpowiednimi wartościami liczbowymi.

Mam coś takiego, podpowie ktoś co tu zmienić?


#include <iostream>
#include<cstdlib>
using namespace std;

bool pierwsza(int n)
{
    if(n<2)
        return false;

    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}

int main()
{
    int n i, count = 0;;

    cout<<"Podaj liczbe: ";
    cin>>n;

    if(pierwsza(n))
        cout<<"Liczba "<<n<<" jest pierwsza"<<endl;
    else
        cout<<"Liczba "<<n<<" nie jest pierwsza"<<endl;

  cout << "Podaj górną granicę: ";
  cin >> n;
  cout << endl;

  int *a = new int;

  if (a == 0)
  {
    cout << "Za mało pamięci" << endl;
     return 0;
  }

   for (i = 2; i < n; i++) a = true;

    for (i = 2; i < n; i++)
     if (a)
      for (int j = i; j*i < n; j++) a = false;

    for (i = 2; i < n; i++)
     if (a)
     {
      count++;
      cout << i << " ";
     }

  cout << endl << "Ile : " << count << endl;

 return 0;
}

Pozostało 580 znaków

kq
2019-01-03 18:34
kq
Moderator C/C++

Rejestracja: 6 lat temu

Ostatnio: 7 godzin temu

Lokalizacja: Szczecin

0

Zmień podejście tak, aby używać Sita Eratostenesa.


Pozostało 580 znaków

2019-01-03 18:48

Rejestracja: 2 lata temu

Ostatnio: 11 miesięcy temu

0

W jaki sposób?

Pozostało 580 znaków

2019-01-03 19:09

Rejestracja: 2 lata temu

Ostatnio: 11 miesięcy temu

0
#include <iostream>
#include<cmath>
using namespace std;

int main()
{
     int n=50000;
     bool liczby[n+1];
     for(int i=0;i<=n;i++)
     {
         liczby[i]=true;
     }
     liczby[i]=false;
     for(int i=2; i<=sqrt(n);i++)
     {
         if(liczby[i]==true)
         for(int j=i+i;j<=n;j=j+i)
         {
             liczby[j]=false;
         }
     }
}
int ile_t;
cin>> ile_t;
for(int i=0;i<ile_t;i++)
{
    int liczba;
    cin>>liczba;
    if(liczby[liczba]==true)
        cout<<"Jest liczba pierwsza " <<endl;
    else
        cout<<"Nie jest liczba pierwsza " <<endl;
}
return 0;
}

co zmienić zeby pasowało do zadania?

Pozostało 580 znaków

2019-01-03 19:23

Rejestracja: 3 lata temu

Ostatnio: 2 minuty temu

0

Czy sito ma być na tyle duże, żeby zindeksować wszystkie potrzebne liczby i tylko robić "lookup", czy sprawdzać tylko do wielkości sita a potem faktoryzować (lub trial division)?


Pozostało 580 znaków

kq
2019-01-03 19:27
kq
Moderator C/C++

Rejestracja: 6 lat temu

Ostatnio: 7 godzin temu

Lokalizacja: Szczecin

0

n jest do 50000 więc raczej z góry trzeba wszystko policzyć.


Acha, już widzę:) - lion137 2019-01-03 19:28

Pozostało 580 znaków

2019-01-03 19:42

Rejestracja: 2 lata temu

Ostatnio: 11 miesięcy temu

0

COŚ trzeba tam zmienić?

Pozostało 580 znaków

2019-01-03 19:42

Rejestracja: 3 lata temu

Ostatnio: 2 minuty temu

1

Gdzie Masz Sito Erastotenesa?


Pozostało 580 znaków

2019-01-03 19:47

Rejestracja: 2 lata temu

Ostatnio: 11 miesięcy temu

0

Tu?

#include <iostream>
#include<cmath>
using namespace std;

int main()
{
     int n=50000;
     bool liczby[n+1];
     for(int i=0;i<=n;i++)
     {
         liczby[i]=true;
     }
     liczby[i]=false;
     for(int i=2; i<=sqrt(n);i++)
     {
         if(liczby[i]==true)
         for(int j=i+i;j<=n;j=j+i)
         {
             liczby[j]=false;
         }
     }
}
int ile_t;
cin>> ile_t;
for(int i=0;i<ile_t;i++)
{
    int liczba;
    cin>>liczba;
    if(liczby[liczba]==true)
        cout<<"Jest liczba pierwsza " <<endl;
    else
        cout<<"Nie jest liczba pierwsza " <<endl;
}
return 0;
}

nie wiem czy pierwszy for jest dobry i jak zrobić ile razy występuje true w tablicy przed indeksem danej liczby?

To jest ten sam program co wyżej? On się nawet nie kompiluje. - Delor 2019-01-03 20:58

Pozostało 580 znaków

2019-01-03 19:56

Rejestracja: 3 lata temu

Ostatnio: 2 minuty temu

0

Sito: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes , implementacja w C++:

#include <iostream>
#include <vector>
#include <iterator>

template <typename I, typename N>
void mark_array(I first, I last, N factor) {
    *first = false;
    while (last - first > factor) {
        first = first + factor;
        *first = false;
    }
}

template <typename I, typename N>
void erastosthenes_sieve(I first, N n) {
    I last = first + n;
    std::fill(first, last, true);
    N i(0);
    N index_square(3);
    N factor(3);
    while (index_square < n) {
        if (first[i]) {
            mark_array(first + index_square, last, factor);
        }
        ++i;
        index_square += factor;
        factor += N(2);
        index_square += factor;
    }
}

int main () {
    std::vector<long> primes;
    std::vector<bool> vec1(50);
    erastosthenes_sieve(vec1.begin(), 50);
    auto  it1 = vec1.begin();
    primes.push_back(2); // dodanie dwójki
    for (int i = 0; i < vec1.size(); i++){ // vec1 - wektor "wysłany" do sita 
        if (it1[i]){ // wskazuje na vec1
            primes.push_back(2 * i + 3);
        }
    }

    for (auto& e : primes) // pierwsze do 2 * 50 
        std::cout << e << " ";
    return 0;
}

Pozostało 580 znaków

2019-01-03 20:10

Rejestracja: 2 lata temu

Ostatnio: 11 miesięcy temu

0

Czyli moje jest do niczego ?

Nie ma tam sita, więc nie spełnia warunków. - lion137 2019-01-03 20:12
@lion137: w jej kodzie jest zrobione sito, patrz tablica liczby. - MarekR22 2019-01-04 11:40
Dodalem post. - lion137 2019-01-04 11:53
Dopiero się tego uczę w próbowałam to zrobić w jak najprostszy sposób bo ten co podałeś ciężko mi zrozumieć niektóre polecenia, dlatego pytałam co zmienić w moim żeby wszystko działało prawidłowo - Nency Black 2019-01-04 12:02
Otwórz sobie wikipedię: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode , i krok po kroku, Zaimplementuj ten algorytm, inaczej się nie Nauczysz i nie Rozwiążesz niczego na egzaminie/interview. - lion137 2019-01-04 12:08

Pozostało 580 znaków

Odpowiedz

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