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

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;
}






0

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

0

W jaki sposób?

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?

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)?

0

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

0

COŚ trzeba tam zmienić?

1

Gdzie Masz Sito Erastotenesa?

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?

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;
}
0

Czyli moje jest do niczego ?

0

Jest ale wszystko w jednej funkcji

0

Nie ma sita. Przypomnij sobie jak robiliście sito w podstawówce na matematyce, a potem porównaj do tego co robi twój kod.

0

Nie wiem jak inaczej to zrobić

0

Nie da się tego jakoś prościej napisać?

0

Eh nie rozumiem jak mam wstawiać to co jest w poleceniu do tego skryptu

0

Na zajęciach robilismy duzo latwiejsze i rzeczy polecen nie ogarniam

0
for (i=2; i<=50000; i++)
{
if (tablica[i] != 0)
{
j = i+i;
while (j<=50000)
{
tablica[j] = 0;
j += i;
}
}

a coś takiego?

0

Przecież ma być z sitem:

void test_number(int n) {
	std::vector<int> primes;
	std::vector<bool> vec1(2500);
	erastosthenes_sieve(vec1.begin(), 2500);
	auto  it1 = vec1.begin();
	primes.push_back(2); 
    for (int i = 0; i < vec1.size(); i++){ 
        if (it1[i]){ 
            primes.push_back(2 * i + 3);
        }
    }
    int i(0);
    for (i = 0; i < primes.size(); i++) {
		if (primes[i] == n) {
			std::cout << i + 1 << " prime\n";
			break;
		}
	}
	if (i == primes.size())
		std::cout << "Not a prime\n";
	
}

int main () {
		test_number(10); // -> Not a prime
		test_number(7); // -> 4 prime
	return 0;
}
0

Ale w tym wszystko działa ok?
ten itl ma error was not declared in this scope i does name a type
Te założenie to w którym miejscu wstawić za te 2500?

0

Kod sita OP jest nie do końca sitem:

	int n=50000;
     bool liczby[n+1];
     int i = 0;
     for( 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;
         }
     }
     for( int i = 0; i < 50; i++) {
		if (liczby[i])
			std::cout << 2 * i + 3 << " "; // -> 3 5 7 9 13 17 25 29 37 41
											// 49 61 65 77 85 89 97
	}
0

To spróbuje też ten z wiki zrobić ale chce przećwiczyć dwa sposoby

#include <iostream>
#include <cmath>
#include <iterator>

using namespace std;

int main ()
{
     int n = 50000;
     bool liczby[n+1];
     for (int i=0; i<=n; i++)
     {
         liczby[i]=true;
     }
     liczby [1] = 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;
{
int i, wynik;
wynik=0;

for (i=0; i<n; i++){
if (liczby[i]==true)
wynik++;
return wynik;

int w;
w=ile;

if (w==0)
cout<<"brak szukanego elementu";
else
cout<<"element  wystepuje  razy";
}
    int liczba;
    cin >> liczba;
    if (liczby [liczba] == true)
        cout << "jest numer pierwsza " << endl;
else
        cout << "Nie jest liczbą pierwsza " << endl;
}

return 0;

}

zastanawiam się w jaki sposób true zliczyć żeby liczył która to liczb pierwsza

0

Tak jak podaje Wikipedia, Wykreślasz dla i^2, i^2 + i, i^2 + 2i,...:

#include <iostream>
#include <vector>
std::vector<int> sieve(int n) {
	std::vector<bool>arr(n);
	std::fill(arr.begin(), arr.end(), true);
	int j{0};
	int k{0};
	for (int i = 2; i * i <= n ; i++) {
		j = i * i;
		k = 1;
		while (j < n) {
			arr[j] = false;
            j = i * i + k * i;
            k++;
		}
	} 
	std::vector<int> result;
	for (int i = 2; i < n; i++) {
		if (arr[i])
			result.push_back(i);
	}
	return result;
}

int main () {
	std::vector<int> p = sieve(20);
	for (auto& e : p)
		std::cout << e << " "; // -> 2 3 5 7 11 13 17 19
	return 0;
}
0

a ograniczenie to w main dać?

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