Java

Welcome to Dream.In.Code
	Getting Java Help is Easy! Join 132,103 Java Programmers for FREE! Get instant access to thousands of Java experts, tutorials, code snippets, and more! There are 2,245 people online right now. Registration is fast and FREE... Join Now! Chat LIVE With a Java Expert

Help for finding largest prime factor of 317584931803

Help for finding largest prime factor of 317584931803, I have written my code.. I need help to set up an array to store facto

Options

MissDesiChick

8 Oct, 2008 - 08:17 PM

Post #1

New D.I.C Head

Joined: 18 Dec, 2007
Posts: 6

My Contributions

java

// 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.

This Post Was Helpful! ^New!


Register for Free to Make These Ads Go Away!

pbl	8 Oct, 2008 - 08:29 PM Post #2
D.I.C Lover Joined: 6 Mar, 2008 Posts: 2,946 Thanked 186 times Dream Kudos: 75 My Contributions	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)
	This Post Was Helpful! ^New!

MissDesiChick	8 Oct, 2008 - 08:36 PM Post #3
New D.I.C Head Joined: 18 Dec, 2007 Posts: 6 My Contributions	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!
	This Post Was Helpful! ^New!

pbl	8 Oct, 2008 - 08:40 PM Post #4
D.I.C Lover Joined: 6 Mar, 2008 Posts: 2,946 Thanked 186 times Dream Kudos: 75 My Contributions	QUOTE(MissDesiChick @ 8 Oct, 2008 - 09:36 PM) 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: 8 Oct, 2008 - 08:42 PM
	This Post Was Helpful! ^New!

MissDesiChick	9 Oct, 2008 - 03:42 AM Post #5
New D.I.C Head Joined: 18 Dec, 2007 Posts: 6 My Contributions	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.
	This Post Was Helpful! ^New!

JeroenFM	9 Oct, 2008 - 06:10 AM Post #6
D.I.C Head Joined: 30 Jun, 2008 Posts: 182 Thanked 9 times Dream Kudos: 100 My Contributions	Interesting use of variables there - former Pascal programmer? You cannot declare variables between a control statement initialisation and statement: java 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: 9 Oct, 2008 - 06:10 AM
	This Post Was Helpful! ^New!

Gloin	10 Oct, 2008 - 03:38 AM Post #7
On MeD.i.Cation Joined: 4 Aug, 2008 Posts: 717 Thanked 46 times My Contributions	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.
	This Post Was Helpful! ^New!