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

Odpowiedz Nowy wątek
2014-12-24 21:40
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;
}

Pozostało 580 znaków

2014-12-24 21:54
1

Sito Eratostenesa.

Pozostało 580 znaków

2014-12-24 21:55
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.

edytowany 2x, ostatnio: Westen, 2014-12-24 22:00
znam szybszy. zamiast obliczania to wypisz je. - fasadin 2014-12-25 09:40
@fasadin :D ale czy to mieści się w pojęciu algorytm? - Westen 2014-12-25 10:59
Ja znam najszybszy algorytm sortowania liczb. Mianowicie insertion sort. I nie mówcie mi o qsort, mergesort itp bo one się nie liczą. - Sopelek 2014-12-25 11:08
@Sopelek Ale my tu mówimy o znajdowaniu pierwszych liczb a nie o sortowaniu - Westen 2014-12-25 13:17

Pozostało 580 znaków

2014-12-24 21:58
0

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

edytowany 1x, ostatnio: spartanPAGE, 2014-12-24 21:59
Wyczuwam bardzo długą kompilację ;d - Sopelek 2014-12-24 22:48
@Sopelek jednorazową. I nie, nie długą. - spartanPAGE 2014-12-24 23:01

Pozostało 580 znaków

2014-12-24 22:07
0

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

dałem link; Liczby pierwsze podpowiem zawsze są takie same - spartanPAGE 2014-12-24 22:09
ok to w linku jest zbyt skomlikowane - misio23 2014-12-24 22:22
to wróć, jak podstawowe szablony nie będą dla Ciebie zbyt skomplikowane. - spartanPAGE 2014-12-24 22:39

Pozostało 580 znaków

2014-12-24 22:14
sig
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.

wyrzuca mi taki bład [Error] could not convert '{2, 3, 5}' from '<brace-enclosed initializer list>' to 'std::vector<int>' - misio23 2014-12-24 22:20
@misio23 - odpowiadaj w postach; - furious programming 2014-12-24 22:34

Pozostało 580 znaków

2014-12-24 22:50
sig
0

Zawsze możesz ograniczyć tą linię do

vector <int> pierwsze; 

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

Pozostało 580 znaków

2014-12-24 23:10
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

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-12-25 00:27
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);
edytowany 2x, ostatnio: Azarien, 2014-12-25 00:29

Pozostało 580 znaków

2014-12-25 07:26
sig
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.

Pozostało 580 znaków

2014-12-25 08:33
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

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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