Program liczący sumę liczb pierwszych działa zbyt wolno

0

Mam program który liczy sumę liczb pierwszych. Działa jednak zbyt wolno, jak go zmienić, aby był szybszy?

#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
 
 bool czy_pierwsza(int n)
{
    for(int i = 2; i * i <= n; i++)
        if (n % i == 0)                
            return false;             

     return true;                      
}
 
long long sum (int a, int b)
 {
 	long long suma=0;
      for (int i = a; i <= b; i++) {
         if (!czy_pierwsza(i)) {
          continue; 
  }
 
  suma += i;
   }	
 cout<<suma<<endl;	
}

int main()
{	

int a,b,n;


for(cin>>n;n--;sum(a,b))  cin>>a>>b; 


        return 0;
}
1

Sito Eratostenesa.

0

Przedstawię Ci najszybszy szybki algorytm jaki ja znam na obliczenie liczb pierwszych(Jeśli ktoś zna szybszy to nich się podzieli, ale bez sito eratostenesa).

#include <stdio.h>
 

bool prime(int n)
{
	int i;
	if(n % 2 == 0) return(n==2);
	if(n % 3 == 0) return(n==3);
	if(n % 5 == 0) return(n==5);
	
	for(i = 7;i*i<=n;i+=2) if(n % i == 0) return 0;

	return 1; // jesli liczba jest liczba pierwsza zwroc true
}


int main(void)
{
  int i,n;
  n = 100;
  for(i=2; i<=n;i++) if(prime(i)) printf("%d\n",i);
  
}

Jeśli czegoś nie zrozumiesz to pisz.

0

Liczby pierwsze są zawsze takie same, dlatego najlepiej jest trzymać je już obliczone LUB obliczać je podczas kompilacji za pomocą szablonów.

0

Co to znaczy "najlepiej jest trzymać je już obliczone"? gdzie i jak?

0

Podejrzewam że to do szkoły, więc taki program

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

using namespace std;

bool pierwsza(int);

vector <int> pierwsze = {2, 3, 5};

int main()
{
    int najw = 50, suma = 10;
    for (int i = 3; i <= najw; i++)
    {
        if (pierwsza(i) == true) suma += i;
    }
    cout << suma << endl;
}
bool pierwsza(int liczba)
{
    int pierw = int(sqrt(liczba));
    int i = 0;
    while (pierwsze[i] <= pierw)
    {
        if (liczba % pierwsze[i] == 0) return false;
        i += 1;
    }
    pierwsze.push_back(liczba);
    return true;
}

zostanie lepiej przyjęty.

0

Zawsze możesz ograniczyć tą linię do

vector <int> pierwsze; 

a najmniejsze pierwsze (2, 3, 5) push_back-ami dodać

0
misio23 napisał(a):

wyrzuca mi taki bład [Error] could not convert '{2, 3, 5}' from '<brace-enclosed initializer="initializer" list="list">' to 'std::vector<int>'

  • ustaw standard kompilatora na C++11
0

wyrzuca mi taki bład [Error] could not convert '{2, 3, 5}' from '<brace-enclosed initializer list>' to 'std::vector<int>'

Masz albo kompilator który nie obsługuje tej nowinki, albo trzeba specjalnie włączyć tryb C++11. Pod GCC odpowiada za to parametr --std=c++11.

Jeśli się nie da to pozostaje jedynie

vector <int> pierwsze;
...
pierwsze.push_back(2);
pierwsze.push_back(3);
pierwsze.push_back(5);
0

W sumie rozwiązanie Azariena może być nawet lepsze, można by if-ami uwzględnić sytuację w której "liczymy sumę pierwszych" np do 4. Przypadek mocno skrajny, ale możliwy. Swoją drogą autor tematu powinien poszukać w moim kodzie pewnego błędu.

0

ok , już ustawiłem ten standard, ale program ma liczyć nie jedną sumę tylko tyle ile użytkownik poda np.
3
od 4 do 5 to 5
od 3 do 6 to 8
od 10 do 14 to 24

0

Czyli pamiętasz w jakiejś zmiennej do jakiej liczby sprawdziłeś, a potem albo uruchamiasz funkcję pierwsza dla brakujących, albo też od razu szukasz w wektorze najmniejszej pierwszej spełniającej minimum, i dodajesz aż dojdziesz do pierwszej większej niż wprowadzone maksimum/końca wektora. Bez problemu powinieneś poradzić sobie z takimi przeróbkami.

0

sito i sumy częściowe powinno starczyć.

 #include <iostream>
using namespace std;

#define MAX_VALUE 10000
bool isPrime[MAX_VALUE+1];
int sum[MAX_VALUE+1];

void sito()
{
    for (int i = 2; i <= MAX_VALUE; i++) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i*i <= MAX_VALUE; i++)
        if (isPrime[i])
            for (int j = i*i; j <= MAX_VALUE; j += i) isPrime[j] = false;

    int last = 0;
    for (int i = 1; i <= MAX_VALUE; i++)
    {
        if (isPrime[i])
        {
            sum[i] = last + i;
            last = sum[i];
        }
        else sum[i] = last;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    sito();
    int n;
    cin >> n;
    while (n--)
    {
        int a, b;
        cin >> a >> b;
        cout << sum[b] - sum[a-1] << endl;
    }
}

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