prime numbers program

Discussion in 'OT Technology' started by notwist, Oct 21, 2005.

1. notwistActive Member

Joined:
Nov 8, 2004
Messages:
5,738
0
Hi, i have a programming assignment i need to write. Basically, it has check each number from 1 to 1000 and if it's a prime number, it will print it. I was just wondering.. What is the simplest way for thsi to be done? I'm supposed to write this in MIPS but i figured if i wrote it in C++ first, i can just convert into MIPS language. Any takers?

2. TkWell-Known Member

Joined:
Dec 23, 2001
Messages:
23,236
338
Location:
nw iowa
lol
i had to do this one earlier this year, easy as hell

3. cmsurferºllllllº

Joined:
Jun 6, 2003
Messages:
5,079
0
Location:
NJ
I think everyone who took a programming class had to do something like that...

Are you asking how to code it or how to functionally do it?

4. TkWell-Known Member

Joined:
Dec 23, 2001
Messages:
23,236
338
Location:
nw iowa
Code:
```#include<iostream>
#include<stdlib.h>

using namespace std;

int main()
{
int i = 1;

while(i<=20)
{
if(i%2>0)
{
cout << i << " is prime..." << endl;
}

i++;
}

system("pause");
return 0;
}```

Joined:
Dec 23, 2001
Messages:
23,236
338
Location:
nw iowa
modulus ftw

6. Penguin ManProtect Your Digital Liberties

Joined:
Apr 27, 2002
Messages:
21,696
0
Location:
Edmonton, AB
That will get all odd numbers, not just primes. For example, 9%2 = 1, but 9%3 = 0, so 9 is not prime. That's on the right track, it just needs to check more numbers.

On a side note, this is a wildly inefficient, although simple, way to check for prime numbers. There are more efficient algorithms, although given the nature of the assignment, my guess is that this obvious method is what they're expecting.

7. notwistActive Member

Joined:
Nov 8, 2004
Messages:
5,738
0
im asking how to do it functionally. my guess as to how to do it would be to send each number from 1 to 1000 to a seperate functin that checks whether it is prime or not.. This function will start from 1 and increase until it is equal to the number sent to the function. This functino will divide the number being checked by the counter variable (the variable that will increment for each loop) and if the remainder is 0 then blah blah.. This is where i get confused and lost

been a while since i've taken a programming course and i hate this assembly language bullshit. Can anyone explain the most efficient and easiest way to do this?

8. YoshiemasterNew Member

Joined:
Sep 17, 2005
Messages:
1,972
0
Location:
Raleigh, NC

me too, i did it for java though.

9. Penguin ManProtect Your Digital Liberties

Joined:
Apr 27, 2002
Messages:
21,696
0
Location:
Edmonton, AB
No reason to write a separate function, you can just use a nested loop. However, it's better coding style to use a separate function.

Hint: You don't need to check each number against each number less than it. You only need to check it against half those numbers.

Also, you can compile C to assembly language. It'll give you x86 assembly, not MIPS, but it may give you some hints.

10. CyberBulletsI reach to the sky, and call out your name. If I c

Joined:
Nov 13, 2001
Messages:
11,865
0
Location:
here is the 1st year prime program i had to write in java. super simple, hopefully this helps

Code:
```public class Prime {

private void Prime(int number){
// lets the user know that the number was valid and it is calculating primes
System.out.println(number + " accepted! Calculating Primes...");

// loop through the numbers from 1 to final number (specified by user)
for(int c = 1;c <= number; c++){
// pass the number of the loop value to findPrime
if(findPrime(c)){
// if findPrime is true, it spits this out
System.out.println(" "+ c + " is prime!");
}
}
}

private boolean findPrime(int number){
// variable delcaration
int divisor = 2; // 1st point to start for prime numbers since the only prime even number is 2
boolean isPrime = true; // needs to be true to allow the while loop to start

// while the test number is still prime, and the divisor is half of the test number
while((isPrime) && (divisor <= number / 2)){
// checks to see if there is a remainder
if(number % divisor == 0){
// if there is, break the while loop by turning isPrime to false
isPrime = false;
}else{
// otherwise increment divisor to try the next number in the set
divisor++;
}
}
// returns if the test number was prime or not
return isPrime;
}

public static void main(String[] args) {
// Checks to see if the number inputed is really a valid Integer (whole number)
Prime prime = new Prime();
try{
// if it is, start the rest of the program
prime.Prime(Integer.parseInt(args[0]));
}catch(NumberFormatException nfe){
// if it isnt, throw a NumberFormatException error
System.out.println("Error: " + args[0] + " is not a valid whole number! \n Please Try Again!");
}
}
}
```

11. notwistActive Member

Joined:
Nov 8, 2004
Messages:
5,738
0
hmm i still cant figure out the actually checking of the numbers. can you maybe write down the pseudocode or actual code?

12. notwistActive Member

Joined:
Nov 8, 2004
Messages:
5,738
0
hmm i dont really know java.. at all

13. CyberBulletsI reach to the sky, and call out your name. If I c

Joined:
Nov 13, 2001
Messages:
11,865
0
Location:
umm you can read the comments cant you? its not all that different from C++.

If i get bored tonight, I'll write it up in asm.

14. Penguin ManProtect Your Digital Liberties

Joined:
Apr 27, 2002
Messages:
21,696
0
Location:
Edmonton, AB
What exactly don't you understand? How to figure out if a number is prime?

15. CyberBulletsI reach to the sky, and call out your name. If I c

Joined:
Nov 13, 2001
Messages:
11,865
0
Location:
what you do is set a divisor number divisor that goes between 2 and 1/2 the test number, and have it loop through. as it passes, increment the divisor number by 1.

eg 1: If your test number is 10, your test divisor number will run between 2 and 5
while(test number isnt prime and test divisor => 5)
test 1 - if(10 % 2 == 0); its true, so it fails since only 1 and the test number divide ito a prime number

eg 2: If your test number is 7, your test divisor number will run between 2 and 3
while (test number isnt prime and test divisor => 3)
test 1 - if(7 % 2 == 0); its false, so divisor number is incremented, and the test keeps happening
test 2 - if(7 % 3 == 0); its false, so divisor number is incremented, here the while loop will break since 4 is bigger then 3. no flags were set so the number is prime.

does that make any more sense?

16. deusexaetheraOT Supporter

Joined:
Jan 27, 2005
Messages:
19,712
0
Declare x as float
Declare y as integer
Declare prime as boolean

Run a loop x = 1 to 1000 in steps of 1
Set prime = true
Run another loop y = 2 to x - 1 in steps of 1
If x/y (decimal division) == x\y (integer division) then prime = false
End another loop
If prime == true then print x
End a loop

This will test every number between 1 and 1000 to see if there are any numbers between 2 and itself that divide cleanly with no decimal places and prints out the ones that survive all the tests.

17. peerkNew Member

Joined:
Mar 14, 2005
Messages:
984
0
When checking if a number is prime you only need to do a mod with up to the squareroot of the number. No need to check up to number/2.

So if you wanted to test if 100 was prime, you would only need to test numbers 2 through 10.

18. notwistActive Member

Joined:
Nov 8, 2004
Messages:
5,738
0
i see. too bad mips doesnt have a squareroot command or is there anothe way to find the square root?

19. TkWell-Known Member

Joined:
Dec 23, 2001
Messages:
23,236
338
Location:
nw iowa
damnit.......... i guess i suck

20. PeyompNew Member

Joined:
Jan 11, 2002
Messages:
14,017
0
wtf kind of thread is this? He just wants someone to do it for him.

21. Penguin ManProtect Your Digital Liberties

Joined:
Apr 27, 2002
Messages:
21,696
0
Location:
Edmonton, AB

And if you don't understand the basic algorithm for determining whether a number is prime, perhaps computer science is not your calling in life.

Joined:
Nov 13, 2001
Messages:
11,865