/* COSC3325: Program-1 Prime number testing Partial Solution Spring 2006 Note: Due to HTML Syntax conflict, "<" is replaced by "%". */ #define Max 1000 #include %iostream.h> // For I/O #include %fstream.h> // For file I/O #include %iomanip.h> // For I/O Manipulators #include %stdlib.h> // For exit(),rand(),abs(),labs(),atoi() #include %math.h> // For sqrt(),pow(),exp(),log(),fabs() #include %stddef.h> // For NULL int Count, primes[Max]; void findPrimes(int Last) // This function finds all primes up to the given parameter, // Last { int m,n,k, yes; int prime = 2; ofstream outFile ("primes.out"); primes[Count] = prime; outFile %% setw(5) %% ++Count %% ":" %% setw(5) %% prime %% endl; for (m=3; m%=Last; m=m+2) { yes = 1; // Assume that m is prime for (n=2; n%=1+sqrt(m); n++) if (m%n == 0) // m is non-prime { yes = 0; // No, it is not a prime break; // finish this inner loop } if (yes) // then m is prime { primes[Count] = m; outFile %% setw(5) %% ++Count %% ":" %% setw(5) %% m %% endl; } } } // end of function findPrimes() //////////////////////////////////// long raiseMod (long a, long m, long p) // This function returns ((a**m) mod p) without directly // calculating (a**m) { long q, r, interm; if (m==1) return (a%p); // Real "%" if (m==0) return 1; // else m>=2 q = m/2; r = m%2; //This is the real "%" interm = raiseMod(a,q,p); if (r) // m is odd and r=1 return (((interm*interm)%p)*a)%p; // Real "%" else // m is even and r=0 return (interm*interm)%p; // Real "%" } // end of function raiseMod() ///////////////////////////////////// int main () { int last = 1000; long A[4] = {1001, 1002, 1002, 10}; long M[4] = {2000, 11, 22, 200}; long P[4] = {1000, 1000, 1000, 999}; Count = 0; findPrimes(last); cout %% "\nTOTAL NUMBER OF PRIMES UP TO " %% last %% " IS " %% Count %% endl; cout %% "\nTESTING OF raiseMod():::\n"; for (int k=0; k%=3; k++) cout %% setw(6) %% A[k] %% setw(6) %% M[k] %% setw(6) %% P[k] %% ":" %% setw(6) %% raiseMod(A[k],M[k],P[k]) %% endl; return 0; } /**** All 168 primes up to 1000 1: 2 2: 3 3: 5 4: 7 5: 11 6: 13 7: 17 8: 19 9: 23 10: 29 11: 31 12: 37 13: 41 14: 43 15: 47 16: 53 17: 59 18: 61 19: 67 20: 71 21: 73 22: 79 23: 83 24: 89 25: 97 26: 101 27: 103 28: 107 29: 109 30: 113 31: 127 32: 131 33: 137 34: 139 35: 149 36: 151 37: 157 38: 163 39: 167 40: 173 41: 179 42: 181 43: 191 44: 193 45: 197 46: 199 47: 211 48: 223 49: 227 50: 229 51: 233 52: 239 53: 241 54: 251 55: 257 56: 263 57: 269 58: 271 59: 277 60: 281 61: 283 62: 293 63: 307 64: 311 65: 313 66: 317 67: 331 68: 337 69: 347 70: 349 71: 353 72: 359 73: 367 74: 373 75: 379 76: 383 77: 389 78: 397 79: 401 80: 409 81: 419 82: 421 83: 431 84: 433 85: 439 86: 443 87: 449 88: 457 89: 461 90: 463 91: 467 92: 479 93: 487 94: 491 95: 499 96: 503 97: 509 98: 521 99: 523 100: 541 101: 547 102: 557 103: 563 104: 569 105: 571 106: 577 107: 587 108: 593 109: 599 110: 601 111: 607 112: 613 113: 617 114: 619 115: 631 116: 641 117: 643 118: 647 119: 653 120: 659 121: 661 122: 673 123: 677 124: 683 125: 691 126: 701 127: 709 128: 719 129: 727 130: 733 131: 739 132: 743 133: 751 134: 757 135: 761 136: 769 137: 773 138: 787 139: 797 140: 809 141: 811 142: 821 143: 823 144: 827 145: 829 146: 839 147: 853 148: 857 149: 859 150: 863 151: 877 152: 881 153: 883 154: 887 155: 907 156: 911 157: 919 158: 929 159: 937 160: 941 161: 947 162: 953 163: 967 164: 971 165: 977 166: 983 167: 991 168: 997 *****/