Przyspieszenie programu pokazującego dzielniki danej liczby

program pokazuje dzielniki liczby ale jest wolny:-(

coś można przyspieszyć ?

#include <iostream>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   
    long long int l;
    cin >> l;
    for (long long int i = l; i > 0; i--)
    {
        if (l % i == 0)
            cout << l / i <<" ";
    }
    return 0;
}

Oczekuje się rozwiązania działającego w czasie proporcjonalnym do pierwiastka z N (liczba naturalna, której dzielników szukamy).
Może gdy znajdziemy dzielnik x, mamy też dzielnik N / x ale nie wiem jak to zrobić :-(

Masz te dzielniki wypisywać w jakiejś konkretnej kolejności? Jak nie, to po prostu w pętli do sqrt(l) wypisuj i i l / i, w przeciwnym wypadku zapamiętaj sobie dzielniki mniejsze, a potem wypisz wszystkie w żądanej kolejności.

Taka uwaga czytelnościowa na marginesie -- nie ma chyba gorszej nazwy zmiennej niż l (małe L) -- może z nim jedynie konkurować O (duże o)...

Zmieniłem ale dalej za wolny :-(

#include <iostream>
 
using namespace std;
 
int main()
{
 ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    for(int i=1; i<=n/2; i++)
    {
        if(n % i == 0)
            cout << i << " ";
    }
    cout << n;
    return 0;
}

To ze spoja? Poza tym sqrt i dzielenie to różne działania.

kq napisał(a):

To ze spoja?

nie
http://solve.edu.pl/tasks/view/12

Jak brzmi odpowiedź na moje pytanie?

Masz te dzielniki wypisywać w jakiejś konkretnej kolejności?

Mialeś chyba "blind spot", wszystkim się zdarza:). @kq napisał Ci dokładnie co trzeba zrobić, jeśli nie Potrzebujesz jakiejś specyficznej kolejności, to:

for (int i = 1; i < sqrt(n) ;i++){
	if ( n % i == 0)
		cout << i << " " << n / i << " "; 
	}

Już lepiej tak:

for (int i = 1; i * i <= n; i++){

kq napisał(a):

Jak brzmi odpowiedź na moje pytanie?

Masz te dzielniki wypisywać w jakiejś konkretnej kolejności?

w kolejności rosnącej

wejście 8
wyjście 1 2 4 8

To zrób coś takiego:

std::vector<int> buf;
buf.reserve(256);
for(int i = 1; i*i <= n; i++) {
    if(n % i == 0) {
        std::cout << i << ' ';
        if(i * i != n)
            buf.push_back(n/i);
    }
}
std::copy(buf.rbegin(), buf.rend(), std::ostream_iterator<int>(std::cout, " "));

https://wandbox.org/permlink/2tXJi5CCjHoaQxWe

@kq: Jeśli dzielnikiem jest pierwiastek z n to chyba dubluje go w wyniku?

Tak jak powyżej, albo używając forward_list, nie wiem czy nie będzie szybciej.

for (int i = 1; i * i <= n ;i++){
    if ( n % i == 0){
        cout << i << " "; 
        if ( i* i ! = n)
			nums.push_front(n / i);	
		}
    }
    for (auto & e : nums)
		cout << e << " ";

@lion137: listy rzadko (bardzo) są szybsze od wektorów... Już lepiej (jeśli trzeba front) użyć deque.

kq napisał(a):

To zrób coś takiego:

std::vector<int> buf;
buf.reserve(256);
for(int i = 1; i*i <= n; i++) {
    if(n % i == 0) {
        std::cout << i << ' ';
        if(i * i != n)
            buf.push_back(n/i);
    }
}
std::copy(buf.rbegin(), buf.rend(), std::ostream_iterator<int>(std::cout, " "));

https://wandbox.org/permlink/2tXJi5CCjHoaQxWe

Nie miałem takich funkcji i nie mogę ich użyć :(

To zamień std::copy na dowolną pętlę wyświetlającą kontener i po sprawie. Bo chyba nikt Ci nie zabrania korzystać z dokumentacji elementarnej struktury jaką jest vector.

kq napisał(a):

To zrób coś takiego:

std::vector<int> buf;
buf.reserve(256);
for(int i = 1; i*i <= n; i++) {
    if(n % i == 0) {
        std::cout << i << ' ';
        if(i * i != n)
            buf.push_back(n/i);
    }
}
std::copy(buf.rbegin(), buf.rend(), std::ostream_iterator<int>(std::cout, " "));

https://wandbox.org/permlink/2tXJi5CCjHoaQxWe

Działa dużo szybciej:) ale.... przekracza limit czasu na dwóch testach, niestety nie wiem jakich:( pewnie dla maxymalnych liczb.

Jeszcze taki kod sprawdzałem jak poniżej.
Większość testów przechodzi ale dla kilku ma złe odpowiedzi.
Może ktoś dostrzega błąd ?

#include <iostream>
#include<math.h>
#include<iomanip>
using namespace std;
unsigned long long int tab[10000] = { 0 };

int
main ()
{
  std::ios_base::sync_with_stdio (false);
  cin.tie (0);
  cout.tie (0);

  unsigned long long int a = 0, n = 0, p = 0;
  cin >> a;

  p = sqrt (a);

  for (unsigned long long int i = 1; i <= p; i++)
    {
      if (a % i == 0)
	{
	  cout << fixed << i << " ";
	  tab[n] = a / i;
	  n++;
	}

    }
  while (n--)
    {
      cout << fixed << tab[n] << " ";

    }
  return 0;
}

dla przypomnienia link do zadania - http://solve.edu.pl/tasks/view/12
Może dla 13 latka z 7 klasy SP to za trudne? Może jakieś działania matematyczne trzeba, o których nie mam pojęcia?

Może wydawanie fixed za każdym razem opóźnia? Wystarczy chyba raz na początku, względnie cout.setf(ios::fixed). A w ogóle to potrzebne w tym zadaniu???

koszalek-opalek napisał(a):

Może wydawanie fixed za każdym razem opóźnia? Wystarczy chyba raz na początku, względnie cout.setf(ios::fixed). A w ogóle to potrzebne w tym zadaniu???

A gdzie wstawić: cout.setf(ios::fixed) ?

Przed for. Ale moim zdaniem to w ogóle niepotrzebne. Bo odnosi się do liczb zmiennoprzecinkowych, a Ty używasz całkowitych...