Posted by madwelshboy [send private reply] at October 29, 2002, 11:10:41 AM

Hello, I am VERY new to programming and I need to check if a no is prime, can anyone point me in the right direction

Posted by RedX [send private reply] at October 29, 2002, 12:16:32 PM

if (no == 1 || no == 2 || no == 3 || no == 5 ...)
prime = true;
else
prime = false;

Posted by regretfuldaydreamer [send private reply] at October 29, 2002, 12:20:09 PM

This sounds a little like Homework.

I presume you just set up a loop that divides every number into the number you want to check is prime. Strings shouldn't need to be used at all.

Posted by RedX [send private reply] at October 29, 2002, 12:29:09 PM

you mean like

    num = 4
    if (num % 1 && num % 2 && num % 3 == 0) then prime =  true

?

Then you optimise that by dropping everything after num/2 and dropping all even numbers after 2 and all multiples of 3,4, ...

Posted by regretfuldaydreamer [send private reply] at October 29, 2002, 12:43:33 PM

Simplisticly:

#include <iostream>

void main(){
	bool isPrime = true;
	int numberYouWantToCheck;
	std::cout << "Enter The Number You Want To Check: ";
	std::cin >> numberYouWantToCheck;
	for(int x = 2;x < numberYouWantToCheck ; x++){
		if((numberYouWantToCheck % x) == 0){
			std::cout << x << " divides evenly into " << numberYouWantToCheck << "\n";
			isPrime = false;
		}
	}

	if(isPrime){
		std::cout << "The number " << numberYouWantToCheck << " is prime\n\n Press enter to continue";
	}
	else{
		std::cout << "The number " << numberYouWantToCheck << " is not prime\n\n Press enter to continue";
	}

	char c;
	std::cin >> c;
}

If you wanted to optomise it you could change the loop check from:
x < numberYouWantToCheck
to
x < ((numberYouWantToCheck/2)+1)

Posted by mop [send private reply] at October 29, 2002, 01:06:11 PM

So thats how you'd impliment the modulous for that. I should have thought simpler..

Posted by RedX [send private reply] at October 29, 2002, 01:19:15 PM

Isn't there some nice math thingy to solve this? Some prove or something?

Posted by regretfuldaydreamer [send private reply] at October 29, 2002, 02:03:39 PM

I think for larger numbers, (Im not certain, you just check if all its preceeding prime numbers divide into it, you don't need to bother checking non primes.(I think, I'm not certain).

Posted by unknown_lamer [send private reply] at October 29, 2002, 02:06:32 PM

You could use Fermat's little thereom, but that is a probalistic algorithm and you can't be 100% sure the number is really prime with it (but it can work very quickly). SICP has a large section on this (it is easier to do in Scheme than C++). The traditional way is to search for the number's smallest divisor by testing two (because if the number isn't divisible by two it can't be divisible by any other even number) and then all of the odd numbers up to the square root of the number (exercise: prove why you only need to go up to the square root).

Posted by regretfuldaydreamer [send private reply] at October 29, 2002, 02:10:44 PM

Because after the square root your just repeating previous ones I think. We're doing something like that for are maths coursewok, find the optimal shape of a pipe, which has a certain perimeter.

Posted by Psion [send private reply] at October 29, 2002, 02:20:25 PM

Testing primality is a very hard problem. It was only late last summer that the first algorithm was published that meets the computer science criterion of being fast enough in a theoretical sense, "polynomial runtime." The algorithm is still intractably slow in practice. As ul mentioned, the best known practical primality testing algorithms use randomness. They almost always give you the correct answer, but there is always a chance they'll lie to you out of sheer cold-bloodedness. Look up the "Miller-Rabin algorithm" if you're interested. Be forewarned: it's not clear why it works so well if you don't know a lot of number theory.

Posted by whizkide [send private reply] at October 31, 2002, 11:42:13 AM

use integer division. i guess thats easy enough.
whizzzz

Posted by rahaydenuk [send private reply] at November 01, 2002, 05:04:33 AM

Try the following link for information about the new polynomial-time primality testing algorithm. Be aware that it's quite (very) maths heavy.

http://www.cse.iitk.ac.in/primality.pdf

Posted by vladimir_l [send private reply] at November 01, 2002, 09:52:21 AM

Isnt the simplest algorthms ERATOSPHERS SIEVE ... hahaha i have the Fortran 77 program to do that somewhere ... hhahah unfortuntely i lost it about 3 years ago.

I think it goes like this you have an array from 1 to n , then you leave out 1 and start with 2 leave two but go to 4 and cross it out then to 6 e.t.c. Then go to 3 ( the next unchecked number ) and repeat the same process and then repeat it with the next unchecked number. After you've finished you have an array of prime numbers : check that the number tested is ot is not there ... this is not a very good solution for big numbers , but it works and prints out a nice array of prime numbers too.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 2 3 X 5 X 7 X 9 XX 11 XX 13 XX 15 XX 17 XX
1 2 3 X 5 X 7 X X XX XX XX 13 XX XX XX 17 XX

1 2 3 5 7 13 17

Posted by arnold [send private reply] at November 01, 2002, 12:38:41 PM

I think you should start by dividing your task into 3 parts.
The first part should be one that declares all numbers less than or equal to zero (0) as non prime.The second part should identify even numbers.If the number is proved even then if it's not 2 then it's not prime.The third should identify odd numbers.If the number is odd to check whether it's prime or not it should be divided by all odd numbers less than it aloop can help you do this.I believe the task can only be achieved by aprogram and not astring.

Posted by Psion [send private reply] at November 01, 2002, 02:29:10 PM

Anyone else who posts to this thread is wasting his time. We've already established:

1) It's easy to write a program that does this.
2) It's hard to write a program that does this quickly.

Posted by mop [send private reply] at November 01, 2002, 06:02:12 PM

Psion, relax, some people enjoy discussing this. I certainly have learnt a lot from this, and if you don't like what we get out of talking about programming and stuff like this, then _your_ wasting your time here.

Posted by arnold [send private reply] at November 02, 2002, 08:48:14 AM

Psion let me hope you were kiding when you said it's hard to write a program that solve the problem quickly.It's so easy to write one in the c language which asks for an integer and before a flick of a second it identifies the integer as prime or not.

Posted by Psion [send private reply] at November 02, 2002, 09:24:06 AM

arnold, try doing that for 100 digit primes.

Posted by vladimir_l [send private reply] at November 02, 2002, 12:31:32 PM

arnold the program is pretty hard to wirte , when i was messing with primes a few years back i found it pretty hard to make eratosphers sieve run for long , as the further you get ( the bigger you limit ) the more crashable it get , and it does it at the start. But i have to agree prime programs are among the funnest.

Posted by gian [send private reply] at November 02, 2002, 04:06:09 PM

"as the further you get ( the bigger you limit ) the more crashable it get"

What? It's only "crashable" if you don't write it well!

Posted by vladimir_l [send private reply] at November 02, 2002, 05:52:20 PM

Well when i was 12 i couldnt really write well , well and it was MS Fortran 3.31, its the memory handling i didnt know how to do. So i got leaks usually with runaway matrixes ... in such simple examples -- i suppose i blame the 486.

Posted by gian [send private reply] at November 03, 2002, 12:14:53 AM

Then why was that at all relevant to anything?

Posted by vladimir_l [send private reply] at November 03, 2002, 06:01:37 AM

nothing i suppose - stupidety !

Posted by arnold [send private reply] at November 04, 2002, 02:21:49 AM

vladimir_l and Psion check this.This program was written using the linux text editor.It's a c-program you give it a number and it tell you the number's status in relation to being prime or not.
#include <stdio.h>
int main(void)
{int N,prime = 0,i;
printf("Please enter a number.\n ");
scanf("%d", &N);
if (N <= 1) {prime = 0;}
else if (N%2 == 0) {
if (N == 2) prime = 1;
else prime = 0;}
else if(N%2==1)
{i=N;while(i>=3){i--;if(N%i==0) prime++;}
if(prime!=0) prime=0;
else prime=1;}
if(prime) printf("%d is prime\n", N);
else printf("%d is NOT prime\n", N);
return 0;}
I think this backs up all my claims.

Posted by vladimir_l [send private reply] at November 04, 2002, 04:55:36 AM

Right now to compile it and get eratoshpers seive going to get a HOUGE prime number and test it. Does it work for only tiny numbers ?

Posted by buzgub [send private reply] at November 04, 2002, 05:02:09 AM

arnold, I disagree. Here's a terminal session on my system, using your primes program. The number used for the long test is my system's INT_MAX.

My machine:

iain@iainsbox:~/playground/arnold$ cat /proc/cpuinfo
processor : 0
vendor_id : AuthenticAMD
cpu family : 6
model : 4
model name : AMD Athlon(tm) Processor
stepping : 2
cpu MHz : 1200.060
(stuff deleted)

iain@iainsbox:~/playground/arnold$ cat /proc/meminfo
total: used: free: shared: buffers: cached:
Mem: 262381568 257732608 4648960 0 3149824 113369088
Swap: 139788288 27234304 112553984
(stuff deleted)

iain@iainsbox:~/playground/arnold$ gcc -o prime prime.c
iain@iainsbox:~/playground/arnold$ time echo 10 | ./prime
Please enter a number.
10 is NOT prime

real 0m0.005s
user 0m0.000s
sys 0m0.000s
iain@iainsbox:~/playground/arnold$ time echo 2147483647 | ./prime
Please enter a number.
2147483647 is prime

real 1m27.883s
user 1m24.540s
sys 0m0.580s

Posted by Psion [send private reply] at November 04, 2002, 05:37:25 AM

Yes, and the number entered here is 1/10th the size of the numbers I asked arnold if his "clever program" could handle quickly. =)

Posted by DragonWolf [send private reply] at November 04, 2002, 05:40:18 AM

lol.. Buzgub, want to run a test on Psions number? You could go on that holiday you always wanted to go on, and when you get back it MIGHT be finished.

Posted by DragonWolf [send private reply] at November 04, 2002, 05:41:24 AM

runing a for loop on a 100 digit long number must be like running an infinite loop ^^

Posted by Psion [send private reply] at November 04, 2002, 05:42:07 AM

Yes, I think arnold's program could be expected to not terminate during the entire lifespan of the universe on a 100 digit prime. (This is not an exaggeration. Work out the math =))

Posted by CViper [send private reply] at November 04, 2002, 05:53:40 AM

I tested a similar program on a maxed int64... I think I had to abort it after a day or so (and it was far from finished)

Posted by DragonWolf [send private reply] at November 04, 2002, 09:33:54 AM

I think the longest executing program I ever made (excluding infinite loops) was one that needed to come up with every possible combination of characters from 5 to 12 in the ASCII char set. This was on a 486 with like a few hundread meg hard disk. I left it for a day or two then found the harddisk was full (even though when I started, all it had was DOS and windows 3.1 ^^) I soon learn't my lesson to never bother trying to do that again ^^

Posted by vladimir_l [send private reply] at November 04, 2002, 10:32:41 AM

DragonWold: I still run a DEC 486 with 170mb HD and it boots linux , gcc , lynx , pico , vi ,tex , fort77 , apache and eveerything i need !!!