Finding square roots

ghosstt · Post by **ghosstt** » Fri Oct 19, 2007 3:28 pm

Hey. I need the best way to find square roots WITHOUT a calculator.

benol · Post by **benol** » Fri Oct 19, 2007 3:30 pm

Why? Need to take a no calculators test? Memorization is your best bet.

ghosstt · Post by **ghosstt** » Fri Oct 19, 2007 3:36 pm

no, its for a project im doing. (program) i need a formula or algorithm that will let me pop a number in, and it will tell me if its prime or not.. whats the best method? (quickest)

vskid · Post by **vskid** » Fri Oct 19, 2007 4:04 pm

How would finding the square root help you find out if a number is prime or not?

You could just have the program divide the number in question by all the whole numbers before it (except itself and 1), and if it doesn't get a whole number as the answer for any of them, then its prime.
Theres probably an easier/faster way, but thats my only idea.

ghosstt · Post by **ghosstt** » Fri Oct 19, 2007 4:19 pm

well, the square root thing was for a previous idea.

The idea you have is what we did in school, though very inefficient for larger numbers..

vskid · Post by **vskid** » Fri Oct 19, 2007 4:29 pm

ghosstt wrote:The idea you have is what we did in school, though very inefficient for larger numbers..

How large? If they're less than 1,000, it'd probably be a good idea to just print out a list of the prime numbers up to 1,000. If you have a graphing calculator, I'm sure you'll be able to find a program that could tell you if a number is prime (check ticalc.org if its a TI).

Post by **Skyone** » Fri Oct 19, 2007 4:35 pm

Code: Select all

int PrimeTest(int x)
{
	x = abs(x);

	if(!x)
	{
		return 1;
	}

	for(int i = 2; i <= sqrt(x); i++)
	{
		if(x % i == 0)
		{
			return 0;
		}
	}
  
	return 1;   
}

Returns 1 if prime, 0 if not.

ghosstt · Post by **ghosstt** » Fri Oct 19, 2007 4:35 pm

wtf is that.. C++?

im using VB.net btw

Post by **Skyone** » Fri Oct 19, 2007 4:38 pm

A function.

ghosstt · Post by **ghosstt** » Fri Oct 19, 2007 4:38 pm

edited post..

how could i apply that.. thats the

i

part of it?

Post by **Skyone** » Fri Oct 19, 2007 4:39 pm

What? Practically every language supports for loops. The i is an increasing integer that is used to assist in checking if x is divisible by a whole number.

Kyo · Post by **Kyo** » Fri Oct 19, 2007 4:41 pm

a variable storing the number of loops the loop has gone thru.
Come on, calling that i is like, the first thing you learn when coding.

edit:

does VB even have for?

ghosstt · Post by **ghosstt** » Fri Oct 19, 2007 4:42 pm

I have no clue how to read that code.. all i know is vb.net..

Kyo · Post by **Kyo** » Fri Oct 19, 2007 4:43 pm

Well, try to translate it. I mean that code is pretty straight forward...

ghosstt · Post by **ghosstt** » Fri Oct 19, 2007 4:51 pm

if factorial of x then its prime? what?