fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <bits/stdc++.h>
  6. #include <time.h>
  7.  
  8. using namespace std;
  9.  
  10. #define sizeN 8000000
  11.  
  12. int arrPrime[sizeN] = {0};
  13. vector<int> PrimesTSqrtN(arrPrime, arrPrime + sizeof(arrPrime) / sizeof(arrPrime[0]));
  14. int countv;
  15. void MarkMultiples(bool mark[],int a,int n)
  16. {
  17.        int i=2,k;
  18.        while((k=i*a)<=n)
  19.        {
  20.               mark[k]=1;  //mark NOT number primes up to srtn(n)
  21.               i++;
  22.        }
  23. }
  24.  
  25.  
  26. void SieveOfEratosthenes(int n)
  27. {
  28.        //bool mark[sizeN];
  29.        bool * mark = new bool[sizeN];
  30.        countv=0;
  31.        if(n>=2)
  32.        {
  33.               mark[n+1]={0};
  34.               int pierwiastek = sqrt(n);
  35.               for(int i=2;i<=pierwiastek;++i)
  36.               {
  37.                      if(mark[i]==0)
  38.                             MarkMultiples(mark,i,n);
  39.               }
  40.               for(int i=2;i<=n;++i) {
  41.                     if(mark[i]==0) {
  42.                         PrimesTSqrtN[countv++]=i;
  43.                     }
  44.               }
  45.  
  46.        }
  47.        PrimesTSqrtN.resize(countv);
  48. }
  49.  
  50. void faktoryzacja(int liczba, int rozmiar) {
  51.     int i, iloraz = 1;
  52.     int liczbaStart = liczba;
  53.     bool wyjdz = false;
  54.     string gwiazdka = "*";
  55.  
  56.     for (i=0; i<rozmiar; i++) {
  57.         if (iloraz == liczbaStart) {
  58.             break;
  59.         }
  60.         if (liczba%PrimesTSqrtN[i]==0) {
  61.             liczba /= PrimesTSqrtN[i];
  62.             iloraz *= PrimesTSqrtN[i];
  63.  
  64.             if (iloraz == liczbaStart) {
  65.                 gwiazdka = "\n";
  66.                 wyjdz = true;
  67.             }
  68.             cout << PrimesTSqrtN[i] << gwiazdka;
  69.  
  70.             if (wyjdz) break;
  71.             --i;
  72.         }
  73.     }
  74. }
  75.  
  76.  
  77. int main()
  78. {
  79.     int ilosc, rozmiar;
  80.     cin >> ilosc;
  81.     vector<int> tmpArr(ilosc);
  82.     clock_t tStart = clock();
  83.     SieveOfEratosthenes(8000000); //~0,22s
  84.     rozmiar = PrimesTSqrtN.size();  
  85.  
  86.  
  87.     for (int k = 0; k < ilosc; k++) {
  88.         cin >> tmpArr[k];
  89.  
  90.         //sprawdzamy czy podana liczba jest liczba pierwsza - tablica jest posortowana wyszukiwanie binarne
  91.         if (std::binary_search(PrimesTSqrtN.begin(), PrimesTSqrtN.end(), tmpArr[k]) || tmpArr[k] == 1) {
  92.             cout << tmpArr[k] << endl;
  93.         }
  94.  
  95.         else  {
  96.             faktoryzacja(tmpArr[k], rozmiar);
  97.         }
  98.     }
  99.     printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  100.  
  101.     /*clock_t tStart = clock();
  102.     for (int k = 0; k < 1000000; k++) {  //~loop rotation 0,04s
  103.         //if (std::find(PrimesTSqrtN.begin(), PrimesTSqrtN.end(),tmpArr[k])!=PrimesTSqrtN.end() || tmpArr[k] == 1) {
  104.         if (std::binary_search(PrimesTSqrtN.begin(), PrimesTSqrtN.end(), k) ||  k == 1) {  //~1,32s, 0,35s on laptop
  105.             //cout << k << endl;
  106.         }
  107.         else  {
  108.             faktoryzacja(k, rozmiar);  //~129,26-136,97 for 1000000 faktoryzacja 0.000137 for one
  109.         }
  110.     }
  111.  
  112.     printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);*/
  113.  
  114.  
  115.     return 0;
  116. }
  117.  
Success #stdin #stdout 0.06s 42544KB
comments (?)
stdin
copy 
6
1
2
42
314
7999999
8000000
stdout
copy 
1
2
2*3*7
2*157
7*199*5743
2*2*2*2*2*2*2*2*2*5*5*5*5*5*5
Time taken: 0.04s
https://ideone.com/dSEIyc
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!