fork download

copy

// **************************************************************************************************
// ************************************* Method - 1 *************************************************
 
// Always works
 
vector<bool> sieve(1e7 + 1, 1); // assign it as global variable
vi prime;
void create_Sieve()
{
    sieve[0] = false, sieve[1] = false;
    for (int i = 2; i * i <= 1e7; i++)
    {
        if (sieve[i] == true)
            for (int j = i * i; j <= 1e7; j += i)
            {
                sieve[j] = false;
            }
    }
 
    for (int i = 2; i <= 1e7; i++)
    {
        if (sieve[i])
            prime.push_back(i);
    }
}
 
map<int, int> prime_fact(int n)
{
    map<int, int> mp;
    for (auto &i : prime)
    {
        if (i * i > n)
            break;
 
        while ((n % i) == 0)
        {
            mp[i]++;
            n /= i;
        }
    }
 
    if (n != 1) // --> bcz n can have at most 1 factor more than sqrt(n)
        mp[n]++;
 
    return mp;
}
 
 
 
// **************************************************************************************************
// ******************************* Method - 2 --> DO NOT USE ****************************************
 
// Only valid for prime factorisation of values ≤ 1e7
 
vector<int> sieve(1e7 + 1); // stores smallest prime factor
void create_Sieve()
{
    // Assuming every value is prime
    for (int i = 0; i <= 1e7; ++i)
        sieve[i] = i;
 
    for (int i = 2; i * i <= 1e7; i++)
    {
        if (sieve[i] == i)
        {
            for (int j = i * i; j <= 1e7; j += i)
            {
                if (sieve[j] == j)
                    sieve[j] = i; // bcz i is smallest prime no. dividing j
            }
        }
    }
}
 
map<int, int> prime_fact(int n)
{
    map<int, int> mp;
	if(n < 2)
		return mp;
 
    while (n != 1)
    {
        mp[sieve[n]]++;
        n /= sieve[n];
    }
 
    return mp;
}

prog.cpp:6:1: error: ‘vector’ does not name a type
 vector<bool> sieve(1e7 + 1, 1); // assign it as global variable
 ^~~~~~
prog.cpp:7:1: error: ‘vi’ does not name a type; did you mean ‘void’?
 vi prime;
 ^~
 void
prog.cpp: In function ‘void create_Sieve()’:
prog.cpp:10:5: error: ‘sieve’ was not declared in this scope
     sieve[0] = false, sieve[1] = false;
     ^~~~~
prog.cpp:10:5: note: suggested alternative: ‘signed’
     sieve[0] = false, sieve[1] = false;
     ^~~~~
     signed
prog.cpp:23:13: error: ‘prime’ was not declared in this scope
             prime.push_back(i);
             ^~~~~
prog.cpp: At global scope:
prog.cpp:27:1: error: ‘map’ does not name a type
 map<int, int> prime_fact(int n)
 ^~~
prog.cpp:55:1: error: ‘vector’ does not name a type
 vector<int> sieve(1e7 + 1); // stores smallest prime factor
 ^~~~~~
prog.cpp:56:6: error: redefinition of ‘void create_Sieve()’
 void create_Sieve()
      ^~~~~~~~~~~~
prog.cpp:8:6: note: ‘void create_Sieve()’ previously defined here
 void create_Sieve()
      ^~~~~~~~~~~~
prog.cpp: In function ‘void create_Sieve()’:
prog.cpp:60:9: error: ‘sieve’ was not declared in this scope
         sieve[i] = i;
         ^~~~~
prog.cpp:60:9: note: suggested alternative: ‘signed’
         sieve[i] = i;
         ^~~~~
         signed
prog.cpp:64:13: error: ‘sieve’ was not declared in this scope
         if (sieve[i] == i)
             ^~~~~
prog.cpp:64:13: note: suggested alternative: ‘signed’
         if (sieve[i] == i)
             ^~~~~
             signed
prog.cpp: At global scope:
prog.cpp:75:1: error: ‘map’ does not name a type
 map<int, int> prime_fact(int n)
 ^~~

Standard output is empty