Help for finding largest prime factor of 317584931803

I have written my code.. I need help to set up an array to store facto

Page 1 of 1

8 Replies - 4195 Views - Last Post: 21 April 2010 - 05:46 PM Rate Topic: -----

#1 MissDesiChick  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 18-December 07

Help for finding largest prime factor of 317584931803

Posted 08 October 2008 - 09:17 PM

// The "LargestPrimeFactor" class.
import java.awt.*;
import hsa.Console;

public class LargestPrimeFactor
{
    static Console c;           // The output console

    public static void main (String[] args)
    {
        c = new Console ();
        String factors = ""; 
        long number, start;
        boolean PrimeNumber, stop_PrimeNumber;

        c.println ("enter the number");
        number = c.readLong ();

        start = number / 2;
        stop_PrimeNumber = false;

        for (long count = start ; count >1 ; count--) 
        {
            if ((number % count) == 0)                          //count is a factor
            {
               c.print (count+" , ");
               PrimeNumber = true;                              // assume count is prime
               for (long i = 2 ; i < (count / 2) ; i++)
                {
           
                    if ((count % i) == 0 )
                         PrimeNumber = false;                   // count is not prime
                }
                if (PrimeNumber)                                // if count is prime display it
                {
                    c.println();
                    c.println ("the largest prime number for the given number " + number + " is " + count);
                    stop_PrimeNumber = true;
                    break;
                }  
            }  
        }
      c.println ("End of Processing! " );     
    } // main method
} // LargestPrimeFactor class


Mod edit - Added code tags.

Is This A Good Question/Topic? 0
  • +

Replies To: Help for finding largest prime factor of 317584931803

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Help for finding largest prime factor of 317584931803

Posted 08 October 2008 - 09:29 PM

And the question is ?
- your code does not compile ? (Post error messages)
- code compiles but I have a run time error (Post error message)
- program runs but does not have the expected behaviour (post actual and expected behaviour)
Was This Post Helpful? 0
  • +
  • -

#3 MissDesiChick  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 18-December 07

Re: Help for finding largest prime factor of 317584931803

Posted 08 October 2008 - 09:36 PM

no my codes do work.. I have tried it in many ways but end up with some error.
In short, i dont know how to apply arrays and use it in java.
i understand that i have to store the values and then display them. but i dont really know the right code for it.

and by this method it takes 5 hours to give me the result for the largest prime factor. i want to make it quicker by using an array and storing the factors in a decreasing order so that the largest prime factor can be found easily and quicker! ;)
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Help for finding largest prime factor of 317584931803

Posted 08 October 2008 - 09:40 PM

View PostMissDesiChick, on 8 Oct, 2008 - 09:36 PM, said:

no my codes do work.. I have tried it in many ways but end up with some error.

Don't want to be rude but:
So it works or it ends up with an error ?
Which type of error ?

You go to your nearest garage and say "What car does not work"
OK, whatis your problem ?
It runs but.... but what ?

This post has been edited by pbl: 08 October 2008 - 09:42 PM

Was This Post Helpful? 0
  • +
  • -

#5 MissDesiChick  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 18-December 07

Re: Help for finding largest prime factor of 317584931803

Posted 09 October 2008 - 04:42 AM

When i run it with an array (which i have guessed), it says that the array was not found even though when i had declared.

I have an attached a copy of my code in which the errors are shown when i use the array.

Now i dont know what mistake have i done. I want to know where i have gone wrong. Could you please help me? :blink:


Attached Image
Here the error is in the For loop.


Attached Image
Here there are 2 errors repeated when i assign the array its value upto 50.
Was This Post Helpful? 0
  • +
  • -

#6 JeroenFM  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 18
  • View blog
  • Posts: 195
  • Joined: 30-June 08

Re: Help for finding largest prime factor of 317584931803

Posted 09 October 2008 - 07:10 AM

Interesting use of variables there - former Pascal programmer?

You cannot declare variables between a control statement initialisation and statement:


for (int i = 0; i < 50; i++)
int a = 5;  // WRONG
{

}

//------

for (int i = 0; i < 50; i++)
{
  int a = 5; // CORRECT
}





The code in your screenshots is different from the code you posted, contrary to my reputation I am not an actual sorceror, psychic or diviner, so I can't magically guess what's going on on your PC - so please, next time, post the actual code.

This post has been edited by JeroenFM: 09 October 2008 - 07:10 AM

Was This Post Helpful? 0
  • +
  • -

#7 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Help for finding largest prime factor of 317584931803

Posted 10 October 2008 - 04:38 AM

This is a typical dynamic programming algorithm.

Given a number you want to find it's biggest prime factor but without memoization you're forced to refactor alot of subproblems which will take alot of times when starting with a huge input.

So what you want to do is save your resultsin an array so that you can quickly notice if a number will factor down to a known result.

A few pointers to begin with.

* When looking for a factor you can start looking from start = sqrt(number) instead of start = number / 2.
proof: sqrt(number) * sqrt(number + 1) > number, I.e Sqrt(number + 1) cannot be a factor of number.

* You my not want to create an array that goes from 2 to sqrt(317584931803) as it will consume alot of memory, if not for this number, it will for a huge number like 317584931803317584931803. Instead, use memoization only for a partition of the possible factors that are the most commonly checked (2 - 100000 these will be checked alot more often than for example the number 68683645321).

* Use -1, 0 or 1 to represent a number in the array that is a prime factor. For all other numbers in the array, let the number denote the biggest factor of this number.
ex:
number[23] = 1, since 23 is a prime and could therefor be the biggest factor.
number[46] = 23, since 46 is not a prime and its biggest factor is 23. This way you can step directly to 23.
number[111] = 37, same as above.

* Keep some variable to store the highest factor found so far. No need to keep searching below it.

If you have further questions. I'll check back later.
Was This Post Helpful? 0
  • +
  • -

#8 ghostrider_  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 20-April 10

Re: Help for finding largest prime factor of 317584931803

Posted 21 April 2010 - 06:21 AM

View PostGloin, on 10 October 2008 - 03:38 AM, said:

This is a typical dynamic programming algorithm.

Given a number you want to find it's biggest prime factor but without memoization you're forced to refactor alot of subproblems which will take alot of times when starting with a huge input.

So what you want to do is save your resultsin an array so that you can quickly notice if a number will factor down to a known result.

A few pointers to begin with.

* When looking for a factor you can start looking from start = sqrt(number) instead of start = number / 2.
proof: sqrt(number) * sqrt(number + 1) > number, I.e Sqrt(number + 1) cannot be a factor of number.

* You my not want to create an array that goes from 2 to sqrt(317584931803) as it will consume alot of memory, if not for this number, it will for a huge number like 317584931803317584931803. Instead, use memoization only for a partition of the possible factors that are the most commonly checked (2 - 100000 these will be checked alot more often than for example the number 68683645321).

* Use -1, 0 or 1 to represent a number in the array that is a prime factor. For all other numbers in the array, let the number denote the biggest factor of this number.
ex:
number[23] = 1, since 23 is a prime and could therefor be the biggest factor.
number[46] = 23, since 46 is not a prime and its biggest factor is 23. This way you can step directly to 23.
number[111] = 37, same as above.

* Keep some variable to store the highest factor found so far. No need to keep searching below it.

If you have further questions. I'll check back later.


let me ask you something..
what tell us that there will not be any prime factors larger than sqrt(n).. for example lets take the number 34.. prime factors are 2 and 17.. if i start near sqrt(n)=6 and going down i will nly find 2, with is not the largest prime factor..
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10664
  • View blog
  • Posts: 39,608
  • Joined: 27-December 08

Re: Help for finding largest prime factor of 317584931803

Posted 21 April 2010 - 05:46 PM

That's a good question (and probably worth the necro-post too). We're assuming that to find the largest prime, you will be looping for each prime you find, reducing the original number as many times as you can. With 34, 2 is the only prime you find from 2-6. So then you try 17%2, which != 0. As the sqrt(17) < 5, you can loop until 6 and prove that 17 is prime.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1