Geek asks and answers

Search for key factors

#include <iostream>
using namespace std;

void whosprime(long long x)
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {
        for(int z = 2; z <= x; z++)
        {
            if((i != z) && (i%z == 0))
            {
                imPrime = false;
                break;
            }
        }

        if(imPrime && x%i == 0)
            cout << i << endl;

        imPrime = true;
    }    
}

int main()
{
    long long r = 600851475143LL;
    whosprime(r);  
}

I am trying to find the simple coefficients of the number 600851475143 indicated by Problem 3 in Project Euler (it asks for the highest primary coefficient, but I want to find all of them). However, when I try to run this program, I do not get any results. Is this due to how long my program takes for such a large number or even with the number itself?

In addition, what are even more effective methods for solving this problem, and do you have any recommendations on how I can be guided by these more elegant solutions, since I work with the problem?

Thanks as always!

+5
source share
12 answers

; . :

define factors(n)

    z = 2

    while (z * z <= n)

        if (n % z == 0)
            output z
            n /= z

        else
            z++

    if n > 1
        output n

++ .

: (, ) :

- . n = 13195. z = 2, 13195 2 1, else z = 3 . n 3 4, z = 5, 13195 5 , 5 13195 5, n = 2639 z = 5 . n = 2639 5 6, 7, 7 n = 2639/7 = 377. z = 7 , 8, 9 10, 11 12, 377/13 = 29 , 13 n = 29. z = 13 z * z = 169, 29, 29 13195, 29. 5 * 7 * 13 * 29 = 13195.

, , , Project Euler # 3. , .

+26

600851475143 int

void whosprime(int x) //<-----fix heere ok?
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {... 
      ...
+3

++ @user448810:

#include <iostream>
using namespace std;

void factors(long long n) {
    long long z = 2;
    while (z * z <= n) {
        if (n % z == 0) {
            cout << z << endl;
            n /= z;
        } else {
            z++;
        }
    }
    if (n > 1) {
        cout << n << endl;
    }
}

int main(int argc, char *argv[]) {
    long long r = atoll(argv[1]);
    factors(r);
}

// g++ factors.cpp -o factors ; factors 600851475143

Perl .
~ 10-15x (Perl 0,01 n = 600851475143)

#!/usr/bin/perl
use warnings;
use strict;

sub factors {
    my $n = shift;
    my $z = 2;
    while ($z * $z <= $n) {
        if ( $n % $z ) {
            $z++;
        } else {
            print "$z\n";
            $n /= $z;
        }
    }
    if ( $n > 1 ) {
        print "$n\n"
    }
}

factors(shift);

# factors 600851475143
+2
# include <stdio.h>
# include <math.h>
void primeFactors(int n)
{
    while (n%2 == 0)
    {
        printf("%d ", 2);
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        while (n%i == 0)
        {
            printf("%d ", i);
            n = n/i;
        }
    }
   if (n > 2)
        printf ("%d ", n);
}
int main()
{
    int n = 315;
    primeFactors(n);
    return 0;
}
+1

: (. ). , , , , , , : -)

1 ( , , , ). , , , , .

0

:

counter = sqrt(n)
i = 2;

while (i <= counter)
    if (n % i == 0)
        output i
    else
        i++
0

, , :

#include <iostream>
using namespace std;

// --> is_prime <--
// Determines if the integer accepted is prime or not
bool is_prime(int n){
    int i,count=0;
    if(n==1 || n==2)
      return true;
    if(n%2==0)
      return false;
    for(i=1;i<=n;i++){
    if(n%i==0)
        count++;
    }
    if(count==2)
      return true;
    else
      return false;
 }
 // --> nextPrime <--
 // Finds and returns the next prime number
 int nextPrime(int prime){
     bool a = false;
     while (a == false){
         prime++;
         if (is_prime(prime))
            a = true;
     }
  return prime;
 }
 // ----- M A I N ------
 int main(){

      int value = 13195;
      int prime = 2;
      bool done = false;

      while (done == false){
          if (value%prime == 0){
             value = value/prime;
             if (is_prime(value)){
                 done = true;
             }
          } else {
             prime = nextPrime(prime);
          }
      }
        cout << "Largest prime factor: " << value << endl;
 }

, , "" "int" .

0

:

    int main()
    {
        int MAX = 13195;

        for (int i = 2; i <= MAX; i++)
        {
             while (MAX % i == 0)
             {
                  MAX /= i;
                  cout <<  i << ", " << flush;   // display only prime factors
             }
        return 0;
    }
0

. , , , , .

int main() {

int num = 0;
cout <<"Enter number\n";
cin >> num;
int fac = 2;  
while (num > 1) {
    if (num % fac == 0) {
        cout << fac<<endl;
        num=num / fac;
    }
    else fac++;
}
return 0;

}

0

:

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll largeFactor(ll n)
{
        ll ma=0;
        for(ll i=2; i*i<=n; i++)
        {
            while(n%i == 0)
            {
                n=n/i;
                ma=i;
            }
        }
        ma = max(ma, n);
        return ma;
}

int main() 
{
    ll n;
    cin>>n;
    cout<<largeFactor(n)<<endl;
    return 0;
}

.

0

Since 600851475143 goes beyond the scope for int, and also for working with one long font here, so here, to solve, we must define our own type here using typedef. Now the range of ll will be around 9,223,372,036,854,775,807.

typedef long long int LL

0
source

Try this code. Absolutely, it is the best and most effective:

long long number;
bool isRepetitive;

for (int i = 2; i <= number; i++) {
    isRepetitive = false;
    while (number % i == 0) {
        if(!isRepetitive){
            cout << i << endl;
            isRepetitive = true;
        }
        number /= i;
    }
}

Enjoy it! ☻

-2
source

More articles:


All Articles