# Help for finding largest prime factor of 317584931803

Page 1 of 1

## 8 Replies - 4330 Views - Last Post: 21 April 2010 - 05:46 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=66845&amp;s=acb43a6c40f54910b9310c44a6e47883&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 MissDesiChick

• New D.I.C Head

Reputation: 0
• 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

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

Reputation: 8362
• Posts: 31,955
• 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

• New D.I.C Head

Reputation: 0
• 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

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

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Help for finding largest prime factor of 317584931803

Posted 08 October 2008 - 09:40 PM

MissDesiChick, 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

• New D.I.C Head

Reputation: 0
• 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?

Here the error is in the For loop.

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

### #6 JeroenFM

• D.I.C Head

Reputation: 18
• 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

• Expert Schmexpert...

Reputation: 235
• 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_

• New D.I.C Head

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

## Re: Help for finding largest prime factor of 317584931803

Posted 21 April 2010 - 06:21 AM

Gloin, 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

• Games, Graphs, and Auctions

Reputation: 11109
• Posts: 41,641
• 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

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }