**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Composite number

Summary

A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, or the unit 1, so the composite numbers are exactly the numbers that are not prime and not a unit.
For example, the integer 14 is a composite number because it is the product of the two smaller integers 2 × 7. Likewise, the integers 2 and 3 are not composite numbers because each of them can only be divided by one and itself.
The composite numbers up to 150 are:
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 129, 130, 132, 133, 134, 135, 136, 138, 140, 141, 142, 143, 144, 145, 146, 147, 148, 150.
Every composite number can be written as the product of two or more (not necessarily distinct) primes. For example, the composite number 299 can be written as 13 × 23, and the composite number 360 can be written as 23 × 32 × 5; furthermore, this representation is unique up to the order of the factors. This fact is called the fundamental theorem of arithmetic.
There are several known primality tests that can determine whether a number is prime or composite, without necessarily revealing the factorization of a composite input.
One way to classify composite numbers is by counting the number of prime factors. A composite number with two prime factors is a semiprime or 2-almost prime (the factors need not be distinct, hence squares of primes are included). A composite number with three distinct prime factors is a sphenic number. In some applications, it is necessary to differentiate between composite numbers with an odd number of distinct prime factors and those with an even number of distinct prime factors.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (2)

Related concepts (15)

A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, or the unit 1, so the composite numbers are exactly the numbers that are not prime and not a unit. For example, the integer 14 is a composite number because it is the product of the two smaller integers 2 × 7. Likewise, the integers 2 and 3 are not composite numbers because each of them can only be divided by one and itself.

Euclid's Elements (Στοιχεῖα Stoikheîa) is a mathematical treatise consisting of 13 books attributed to the ancient Greek mathematician Euclid in Alexandria, Ptolemaic Egypt 300 BC. It is a collection of definitions, postulates, propositions (theorems and constructions), and mathematical proofs of the propositions. The books cover plane and solid Euclidean geometry, elementary number theory, and incommensurable lines. Elements is the oldest extant large-scale deductive treatment of mathematics.

In number theory, a sphenic number (from σφήνα, 'wedge') is a positive integer that is the product of three distinct prime numbers. Because there are infinitely many prime numbers, there are also infinitely many sphenic numbers. A sphenic number is a product pqr where p, q, and r are three distinct prime numbers. In other words, the sphenic numbers are the square-free 3-almost primes. The smallest sphenic number is 30 = 2 × 3 × 5, the product of the smallest three primes.

Related courses (3)

Related lectures (21)

Prime Numbers and Primality Testing

Covers prime numbers, RSA cryptography, and primality testing, including the Chinese Remainder Theorem and the Miller-Rabin test.

Shor Algorithm: Circuit Details II

Explores the Shor algorithm circuit details for efficient number factoring using quantum computing.

Primes: Fundamental Theorem and Sieve of Eratosthenes

Explores primes, the Fundamental Theorem of Arithmetic, trial division, the Sieve of Eratosthenes, and Euclid's Theorem.

MATH-643: Applied l-adic cohomology

In this course we will describe in numerous examples how methods from l-adic cohomology as developed by Grothendieck, Deligne and Katz can interact with methods from analytic number theory (prime numb

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Since the discovery of the utility of the numbers, the human being tried to differentiate them. We decide between them according to whether they are even or odd. Or, according to the fact that they ar

2006We prove an asymptotic formula for squarefree numbers in arithmetic progressions, improving previous results by Prachar and Hooley. As a consequence we improve a lower bound of Heath-Brown for the lea