Display prime numbers

[sigmundccs]

Write a program to load in two integers from the user. Display all the prime numbers between the two integers.

i'm a beginner. i'm problem doing this. can anyone teach me ?

thanks a lot.

[Ganon11]

Sure. One of the first tasks in teaching is assessing what the student (that's you) knows, regarding the problem. So, what do you know about prime numbers? What approaches have you considered taking to solve this problem? What ideas do you have?

[JosAH]

Sure. One of the first tasks in teaching is assessing what the student (that's you) knows, regarding the problem. So, what do you know about prime numbers? What approaches have you considered taking to solve this problem? What ideas do you have?

mathematician: 3 is prime, 5 is prime, 7 is prime so by complete induction all
odd numbers are prime;

physicist: 3 is prime, 5 is prime, 7 is prime, 9, erm, sample data error, 11 is
prime, 13 is prime; yeah the math is ok;

engineer: 2 is prime, 4 is prime, 6 is prime, 8 is prime, yep, all odd numbers
are prime alright.

politician: what's an odd number?

philosopher: what's prime?

kind regards,

Jos ;-)

[Nepomuk]

mathematician: 3 is prime, 5 is prime, 7 is prime so by complete induction all
odd numbers are prime;

physicist: 3 is prime, 5 is prime, 7 is prime, 9, erm, sample data error, 11 is
prime, 13 is prime; yeah the math is ok;

engineer: 2 is prime, 4 is prime, 6 is prime, 8 is prime, yep, all odd numbers
are prime alright.

politician: what's an odd number?

philosopher: what's prime?

kind regards,

Jos ;-)

Computer Scientist: 0 is prime, 1 is prime, memory out of stack error.

Motivator: Every number can be prime, if it wants to!

Priest: I believe, that all numbers were created equally!
(Oh sorry, no religious content allowed... ^^)

Greetings,
Nepomuk

[Ganon11]

Priest: I believe, that all numbers were created equally!

Isn't this really Martin Luther King, Jr.?

[Nepomuk]

Isn't this really Martin Luther King, Jr.?

Fine by me ^^

Then the priest says: "All numbers are equal before god." ;-)

Greetings,
Nepomuk

[Nepomuk]

Some more:

George Orwell: All numbers are prime, but some are more prime than others.

Psychologist: 3 is prime, 5 is prime, 7 is prime, 9 is prime but has an identity crisis, 11 is prime...

Trade Unionist: We will fight for the same right for all odd numbers!

Lawyer: 9 is prime and I'll sue anyone who says otherwise!

Deep Thought: 42!

Greetings,
Nepomuk

[sateesht]

Hi,

Prime Number is a Number which have only two factors 1 and itself.


Cheers,
Sateesh.

[kreagan]

Write a program to load in two integers from the user. Display all the prime numbers between the two integers.

i'm a beginner. i'm problem doing this. can anyone teach me ?

thanks a lot.

You guys are way too funny.

Anyways, finding the prime numbers via brute force (though the most obvious way to solve the problem) is inefficient. When I say brute force, I mean given N, I divide N via all numbers greater than 1 and less than N.

I would read a mathematical theorem: "Fermat's Little Theorem". This theorum helps determine if a number is prime or not. Be aware that this theorem will not always find the prime numbers but give a probability that a number is or isn't prime.

Fermat's Little Theorem in Scheme

[Nepomuk]

You guys are way too funny.

Anyways, finding the prime numbers via brute force (though the most obvious way to solve the problem) is inefficient. When I say brute force, I mean given N, I divide N via all numbers greater than 1 and less than N.

I would read a mathematical theorem: "Fermat's Little Theorem". This theorum helps determine if a number is prime or not. Be aware that this theorem will not always find the prime numbers but give a probability that a number is or isn't prime.

Fermat's Little Theorem in Scheme

Well, the "brute force" method is certainly more accurate, and you don't have to check all numbers from 1 to N, but only from 2 (or if you only check every second number: from 3) to sqrt(N). Saves a lot of time...

Greetings,
Nepomuk

PS.: I wrote a little method, that does exactly that and it calculated all Primes between 1 and 10000000 in only a few minutes. So it's not that inefficient... ^^

[JosAH]

You guys are way too funny.

Anyways, finding the prime numbers via brute force (though the most obvious way to solve the problem) is inefficient. When I say brute force, I mean given N, I divide N via all numbers greater than 1 and less than N.

I would read a mathematical theorem: "Fermat's Little Theorem". This theorum helps determine if a number is prime or not. Be aware that this theorem will not always find the prime numbers but give a probability that a number is or isn't prime.

Fermat's Little Theorem in Scheme

For any number less than 2^64 every locally smart method does fine; Fermat's
little trick doesn't buy you much if you want certainty; it just has nice theoretical
applications; algorithmically it can't do much more for you than being a stochastic
test.

kind regards,

Jos

[kreagan]

For any number less than 2^64 every locally smart method does fine;

Good Point

Fermat's
little trick doesn't buy you much if you want certainty; it just has nice theoretical
applications; algorithmically it can't do much more for you than being a stochastic
test.

If the test fails, the number is guarrenteed to be a non-prime number. By using Fermat's Little Theorem as a preliminary check, then throughly checking if the number is indeed a prime (using a locally smart method like you said), you increase speed and guareentee accuracy.

As for the Fermat's Test, every source I have read states it is " adequate for practical purposes."

[JosAH]

As for the Fermat's Test, every source I have read states it is " adequate for practical purposes."

It is in theory but it isn't in practice; you do have the sources available of all
the core classes; have a look at the BigInteger.isProbablePrime() method;
it's much better, it's a combination of the Miller-Rabin test and the Lucas test
if I'm not mistaken. Fermat's 'little' theorem is a nice theoretical thingy.

kind regards,

Jos

[kreagan]

It is in theory but it isn't in practice; you do have the sources available of all
the core classes; have a look at the BigInteger.isProbablePrime() method;
it's much better, it's a combination of the Miller-Rabin test and the Lucas test
if I'm not mistaken. Fermat's 'little' theorem is a nice theoretical thingy.

kind regards,

Jos

Awesome, thanks a lot!