przyspieszenie dzialajacego programu

Question

 program już działa tak jak należy i zalicza mi wiekszosc lecz w niektorych dalej jest przekroczenie limitu czasowego. Czy dałoby się jakos ten program przyspieszyc ?

#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
bool sprawdz_czy_pierwsza(int a)
{
    if(a<2)
        return false;
    for(int i=2; i<=sqrt(a); i++)
        if(a%i==0)
            return false;
    return true;

}

int main()
{
    int l_testow,liczba, maks;
    scanf("%d",&l_testow);
    for(int i=0; i<l_testow; i++)
    {
        scanf("%d",&liczba);
        int *tablica;
        tablica = new int [liczba+1];
        for(int j=0; j<=liczba; j++)
        {
            tablica[j]=j;
            maks=tablica[0];
            if( tablica[j]>maks)
                maks=tablica[j];
        }
        if(maks!=0)
        {

            do
            {
                if(sprawdz_czy_pierwsza(maks)==1)
                {
                    printf("%d\n",maks);
                    continue;
                }
                maks--;
                if(sprawdz_czy_pierwsza(maks)==1)
                {
                    printf("%d\n",maks);
                    continue;
                }
            }
            while(sprawdz_czy_pierwsza(maks)!=1);
            delete [] tablica;
        }
    }
    return 0;
}

 

Comments

Pytanie dotyczy serwisu SPOJ lub podobnego? Zmień więc kategorię na odpowiednią oraz podaj link do treści zadania.

---

Oto treść zadania:

Zdolniak hoduje kurę, która okazała się bardzo uzdolniona matematycznie. Zjada ona tylko liczbę
pierwszą ziaren. Zdolniak karmi ją w szczególny sposób. Otóż wysypuje jej ziarna w pewną ilość
kupek, z których każda jest nie mniejsza niż poprzednia, a kura zjada z każdej z nich największą
możliwą liczbę pierwszą ziaren.
Wejście:
W pierwszej linii liczba całkowita k oznaczająca ilość zbiorów ziaren (2 ≤ k ≤ 5000). W kolejnych
k wierszach liczba zi (2 ≤ zi ≤ 5000, 1 ≤ i ≤ k)równa ilości ziaren na i-tej kupce.
Wyjście:
W każdym i wierszu jedna liczba całkowita równa ilości ziaren zjedzonych przez kurę Zdolniaka

Answer 1

Zrób sito Eratostenesa. Nie będziesz musiał ciągle liczyć sprawdzać liczb, które już sprawdziłeś.