prime numbers program

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

  1. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    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? :hs:
     
  2. Tk

    Tk Well-Known Member

    Joined:
    Dec 23, 2001
    Messages:
    23,079
    Likes Received:
    281
    Location:
    nw iowa
    lol
    i had to do this one earlier this year, easy as hell
     
  3. cmsurfer

    cmsurfer ºllllllº

    Joined:
    Jun 6, 2003
    Messages:
    5,079
    Likes Received:
    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. Tk

    Tk Well-Known Member

    Joined:
    Dec 23, 2001
    Messages:
    23,079
    Likes Received:
    281
    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;    
    }
    :hsd:
     
  5. Tk

    Tk Well-Known Member

    Joined:
    Dec 23, 2001
    Messages:
    23,079
    Likes Received:
    281
    Location:
    nw iowa
    modulus ftw
     
  6. Penguin Man

    Penguin Man Protect Your Digital Liberties

    Joined:
    Apr 27, 2002
    Messages:
    21,696
    Likes Received:
    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. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    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 :hs:

    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. Yoshiemaster

    Yoshiemaster New Member

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

    me too, i did it for java though.
     
  9. Penguin Man

    Penguin Man Protect Your Digital Liberties

    Joined:
    Apr 27, 2002
    Messages:
    21,696
    Likes Received:
    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. CyberBullets

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

    Joined:
    Nov 13, 2001
    Messages:
    11,865
    Likes Received:
    0
    Location:
    BC, Canada/Stockholm, Sweden
    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. notwist

    notwist Active Member

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

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    hmm i dont really know java.. at all :wtc:
     
  13. CyberBullets

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

    Joined:
    Nov 13, 2001
    Messages:
    11,865
    Likes Received:
    0
    Location:
    BC, Canada/Stockholm, Sweden
    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 Man

    Penguin Man Protect Your Digital Liberties

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

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

    Joined:
    Nov 13, 2001
    Messages:
    11,865
    Likes Received:
    0
    Location:
    BC, Canada/Stockholm, Sweden
    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. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    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. peerk

    peerk New Member

    Joined:
    Mar 14, 2005
    Messages:
    984
    Likes Received:
    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. notwist

    notwist Active Member

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

    Tk Well-Known Member

    Joined:
    Dec 23, 2001
    Messages:
    23,079
    Likes Received:
    281
    Location:
    nw iowa
    damnit.......... i guess i suck :sad2:
     
  20. Peyomp

    Peyomp New Member

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

    Penguin Man Protect Your Digital Liberties

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

    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.
     
  22. CyberBullets

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

    Joined:
    Nov 13, 2001
    Messages:
    11,865
    Likes Received:
    0
    Location:
    BC, Canada/Stockholm, Sweden
    its not like finding a prime number is hard though. we have posted all the rules in this thread for it.
     

Share This Page