Ask General Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

Need some help with one of the project Euler puzzles. It's the one where you have to find the largest prime factor of 317584931803. I made a method I called isPrime(int x), where you test x % (2 to x^1/2 inclusive) and if any of those is 0, it returns false, otherwise it returns true. Well that helper method worked for the smaller example case (largest prime factor of 13195), but when I tried it for 317584931803, it ran for several minutes and still didn't find the answer, so I killed it. I'm trying the fermat primality test instead for the smaller case, but it doesn't seem very accurate. I'm also worried that I might have problems using that algorithm for the larger case, since there is no nextLong method for the java Random class. Am I on the right track with using the fermat test? Is there another algorithm I should be using?

# ¿ Feb 25, 2008 07:10

Adbot: ADBOT LOVES YOU

# ¿ May 6, 2024 12:26

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

JawnV6 posted:

317584931803 is larger than can be stored in an int.

Yeah I should have mentioned that I used longs for the larger case. That's not the problem, my algorithm works it's just that it's worst case time is horrible for larger stuff, so I was looking for a better alternative.

# ¿ Feb 26, 2008 21:55

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

narbsy posted:

Yeah, just tested now. It took about 30 seconds for 600851475143, the new number for problem 3.

I tried your suggestion and used the new number for the problem, it still did the same thing, ran for about four minutes and I gave up. I'm skipping evens in the primality test and the main method that checks if it's a factor of 600851475143. What kind of prime test are you using?

JawnV6 posted:

Don't check every single integer between 1 and x^.5, build a list of primes and check against just those?

Could you elaborate on this? I kind of get what you mean, but how do I go about building that list?

# ¿ Feb 27, 2008 02:29

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

narbsy posted:

Appa Time! Yeah, I build a list of primes first to test against. Here's my code if you'd like; it's pretty simple. I'm not very complex.

Jesus, I modeled mine more after yours and it gave me the correct answer almost instantly. My old way ran for 15 minutes and still didn't find it. Thanks a lot man.

# ¿ Feb 27, 2008 07:29

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

code:

(define (reverse mylist)
  (if (null? mylist) mylist
      (append (reverse (rest mylist)) (list (first mylist)))))

Can someone walk through this recursion with me? It's really confusing and I can't follow it. I don't understand the base case, how does mylist ever become null?

# ¿ Mar 2, 2008 01:44

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

Oh I see now, now I just have to translate it into java. Thanks.

Edit: drat, I can't get this to work now in Java. I don't think there is a "rest" function for lists in java, so I did this:

code:

public static ArrayList<Integer> reverseListR(ArrayList<Integer> mylist)
	{
		if(mylist==null)
		{
			return mylist;
		}
		
		int current = mylist.get(0);
		mylist.remove(0);
		mylist = reverseListR(mylist);
		mylist.add(current);
		return mylist;
	}

Any ideas?

sd6 fucked around with this message at 03:18 on Mar 2, 2008

# ¿ Mar 2, 2008 02:50

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

csammis posted:

An empty list isn't null in Java, it's just empty. size() == 0.

Right you are, fixed it and it works just fine now. Thanks guys!

# ¿ Mar 2, 2008 05:03

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

Does anyone know of a good intro tutorial online to writing programs that modify behavior of other programs? I'm talking about things like the Steam achievement manager or D2 character editors, but it wouldn't have to be that complex or even have anything to do with games. I just want to understand how people write programs that are dependent on or change the behavior of other existing programs.

# ¿ Nov 6, 2008 06:30

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

ante posted:

This is kinda vague, but there are a few different ways, depending upon what you're trying to do.

Alright I'll give those a look, thanks!

# ¿ Nov 6, 2008 16:41

Adbot: ADBOT LOVES YOU

# ¿ May 6, 2024 12:26

sd6: Jan 14, 2008; This has all been posted before, and it will all be posted again

I have a quick question for those already in the field as professional programmers. I'm in my last year of school for an undergrad degree in CS, and I'd like to get a job as a programmer after graduation. Aside from the actual cs classes that are math/theory, most of the implementation classes are in desktop application programming in Java. Outside of coursework, I'm trying to learn other languages and technologies, and I wanted to ask whether you guys think there will be more need for desktop application programmers, or for web application programmers/web developers. I hope to be skilled at both eventually, but is there one that I should be focused on learning more than the other in regards to getting a job?

# ¿ Sep 9, 2009 05:29

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread